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
![](https://blog.salvatorelabs.com/content/images/2023/09/Screenshot-2023-09-07-at-08.41.20.png)
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:
![](https://blog.salvatorelabs.com/content/images/2023/09/Screenshot-2023-09-07-at-08.39.47.png)
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 returnsfalse
.
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.