Binary Search Tree is a binary tree data structure which has the following properties:
- The left subtree of a node contains only nodes with keys lesser than the node’s key
- The right subtree of a node contains only nodes with keys greater than the node’s key
For each node, there is an upper limit or a lower limit or both on its value. The limits are determined by its ancestors as you can see from the properties above. Further, each node imposes an upper limit on its left subtree (i.e., its left subtree should have a value less than the node’s value) and a lower limit of its right subtree (i.e., its right subtree should have a value greater than the node’s value). Consider this BST:
2
\
4
/
1
Here, the node 2 is the root so it has no restrictions from its ancestors (as it has no ancestor!). Further, it imposes a lower limit of "2" on its right subtree, i.e., all the nodes in its right subtree should be greater than 2.
Now, 4 is greater than 2 so the BST is valid till now. Now, 4 imposes a lower limit on its left subtree so all the nodes in the left subtree should be less than 4. Remember that there was an upper limit too! Considering both limits, all the nodes in the left subtree of 4 should be less than 4 but greater than 2.
1 is within the limits to the BST is valid.
It is clear from the above example that a node changes the upper limit for its left subtree keeping the lower limit to be the same. For the right subtree, it changes the lower limit keeping the upper limit to be the same. The recursive solution below leverages this property.
bool isValidBST(TreeNode* root, int lower=-1, int upper=-1) {
if (root == NULL)
return true;
if ((lower!=-1 && root->val <= lower) || (upper!=-1 && root->val >= upper))
return false;
return isValidBST(root->left, lower, root->val) && isValidBST(root->right, root->val, upper);
}
Time complexity: O(n) where n is the number of nodes
Space complexity: O(h) where h is the height of tree (space of recursion stack)