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.
Input: root = [2,1,3]
Input: root = [5,1,4,null,null,3,6]
Explanation: The root node's value is 5 but its right child's value is 4.
- The number of nodes in the tree is in the range
-2^31 <= Node.val <= 2^31 - 1
A binary search tree is a tree where all the left children of the root have a value less than the root’s value and all the right children of the root have a value greater than the root’s value.
This is the only condition we have to check in order to solve this question.
We will be using recursion to solve this problem and we maintain a low value and a high value. The lowest value of the tree will be on the left-most end and the high value of the tree will be on the right-most end.
So we must not have any value that will be lower than the lowest value possible or any value that will be greater than the highest value possible.
- Start recursion from the root node and set the lowest value as Long.MIN_VALUE and set the highest value as Long.MAX_VALUE.
recursion(root, Long.MIN_VALUE, Long.MAX_VALUE);
- Inside the recursion function, if the node is null, just return true as this is the base condition.
- Check whether the current node value is either less than the lowest value or greater than the highest value. If yes return false as this will not be a binary search tree.
- Else continue our recursion for the left child and right child. For the left child recursion update the highest value as node.data and for the right child recursion, update the lowest value as node.data.
recursion(root.left, low, root.val) && recursion(root.right, root.val, high).
Time and Space Complexity
We are traversing through the whole node, so the time complexity will be O(n) where n = the number of nodes.
The space complexity will be O(h) where h = height of the tree.