LeetCode: 98. Validate Binary Search Tree

The Problem

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Example

Input:  [2,1,3]
Output: true

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -231 <= Node.val <= 231 - 1

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

bool isValidBST(TreeNode* root) {
    vector<int> inorder;
    trasverse(root, inorder);

	for(int i = 1; i < inorder.size(); ++i)
    	if(inorder[i-1] >= inorder[i]) return false;

    return true;
}

void trasverse(TreeNode* root, vector<int> &vec) {
    if (root == NULL) return;
    trasverse(root->left, vec);
    vec.push_back(root->val);
    trasverse(root->right, vec);
}

Here's a breakdown of how the code works:

1. bool isValidBST(TreeNode* root): This is the main function that checks if the binary tree rooted at root is a valid BST. It returns true if it is a valid BST and false otherwise.

2. vector<int> inorder;: A vector named inorder is created to store the in-order traversal of the binary tree. In an in-order traversal, you visit the left subtree, then the current node, and then the right subtree, resulting in a sorted list of values for a valid BST.

3. trasverse(root, inorder);: This line calls the trasverse function to perform an in-order traversal of the binary tree root and populates the inorder vector with the values of the nodes in sorted order.

4. The for loop iterates through the inorder vector from index 1 to the end.

• if (inorder[i-1] >= inorder[i]) return false;: Inside the loop, it checks if the previous value (inorder[i-1]) is greater than or equal to the current value (inorder[i]). If this condition is met, it means that the tree is not a valid BST because a valid BST should have values in ascending order. If this condition is true for any pair of adjacent values, the function immediately returns false.

5. If the loop completes without finding any adjacent values violating the BST property, it means the binary tree is a valid BST, and the function returns true.

6. void trasverse(TreeNode* root, vector<int> &vec): This is a recursive helper function that performs the in-order traversal of the binary tree. It starts at the root node and recursively traverses the left subtree, then appends the value of the current node to the vec vector, and finally recursively traverses the right subtree. This ensures that the values are added to the vector in ascending order.