Task description:
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 1:
Input: root = [2,1,3]
Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -2^31 <= Node.val <= 2^31 - 1]
Reasoning:
Let’s consider the big enough valid binary search tree
The Root of the Tree is marked as black, all the nodes in the left subtree are marked blue and all the nodes in the right subtree are marked red
As you can see blue nodes are less than black at the same time red nodes are bigger than black. Let’s move downwards.
You could make your own examples, results will be the same, because I provide the valid BST. This is exactly what we are asked. We have to verify if given binary tree is valid BST.
I created this animation to show you all possible options
If you pay enough attention some cases are easy to check, for example case for root node with value 20 . Case for node with value 9 does not seem to be easy one.
The reason for this — we need to traverse the entire tree to find out if tree is valid BST from the standpoint of particular node.
It must be obvious for you at this point — there’s no way we can answer to the main question without traversing the entire tree.
To answer the question whether or not the tree is valid we need to answer 3 additional questions:
-
Is the left subtree valid?
-
Is the right subtree valid?
-
Last but not least, all nodes in the left subtree are less than root and all nodes in the right subtree are greater than root
Following this logic, if we answer yes for every single node in the tree — we can say for sure tree is valid. This is essentially what we want and need to do.
Solution:
Usually I provide solution step by step, but this time to make it clear and more easy to grasp the logic behind it, I provide the entire solution first.
public boolean isValidBST(TreeNode root)
{
Integer[] prev = new Integer[1];
return isValidBST(root, prev);
}
public boolean isValidBST(TreeNode root, Integer[] prev)
{
boolean left = true;
if (root.left != null)
{
left = isValidBST(root.left, prev);
}
if (prev[0] != null && prev[0] >= root.val)
{
return false;
}
prev[0] = root.val;
boolean right = true;
if (root.right != null)
{
right = isValidBST(root.right, prev);
}
return left && right;
}
We create the auxiliary/helper method which uses recursion to answer our question.
Apart from taking a node it takes additional Integer[] parameter, essentially it’s just one value which can be updated along the way of exploring the tree. We use inorder depth-first-search. As I said previously, we start from answering the question “is left subtree valid?”. Then we answer one part of the third question, if all the nodes in the left subtree are less than the current node. After we proceed to the second question “Is the right subtree valid?”.
That is it. Initial problem divided into small sub problems turned into the valid solution.
The code above gives us following