You are given a binary search tree.
You need to find out if it is valid or not.
A BST is valid if all the elements in the left tree are less than the current node
And all the elements in the right tree are greater than the current node.
This has to apply for each sub tree.
For example,
The below tree represented by [2,1,3] is valid:
But the given tree represented by
[5,1,4,null,null,3,6]
is invalid.
This is because the node 4 should be greater than the node 5 but it is not..
Also all the nodes right to the node 5 should be greater than 5 but there is a node 3 as well in addition to the node 4 which are smaller than 5.
So the tree is not a valid BST.
Try out the solution here:
https://leetcode.com/problems/validate-binary-search-tree/
Solution:
Hint:
Use DFS or BFS or inorder traversal
Explanation:
There are several approaches to this problem:
- Depth First Search
- Breadth First Search
- Recursive Inorder Traversal
- Iterative Inorder Traversal
Let’s look at each of them.
Approach 1: Depth First Search
In this case you might be tempted to compare each node with its left node value and the right node value.
That is ,
Check if current node value is greater than its left node
Check if current node value is less than its right node
Do this recursively for each node.
But this won’t work for all cases
Consider the below tree:
If you just consider the left and right node values for each node the above tree might appear as a valid BST.
But consider the node 6.
The left node to this is 4 (lesser than 6) and the right node is 7 (greater than 6).
They both obey the lesser than and greater than checks.
But the node 4 is less than the node 5.
This violates the rule:
All nodes right to the node 5 should be greater than 5.
So we can’t use this logic.
Instead we can check for lower and upper bound values for each node.
For the first node 5 there are no bounds.
So lower bound is -infinity and upper bound is +infinity.
For the node 1 left to the node 5,
The lower bound is still -infinity,
But the upper bound is 5, It cannot be equal to or greater than 5.
Similarly if you move right to the node 5.
The lower and upper bounds of the node 6 are 5 and +infinity.
For the next node 4,
The lower bound is 5 , but the value 4 is less than 5 , so the given tree is invalid and we return false.
In short,
For each node , we check if the value of the given node lies within the lower and upper bound.
here is the code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
boolean valid;
public boolean isValidBST(TreeNode root) {
return dfs(root,null,null);
}
public boolean dfs(TreeNode node,Integer low,Integer high){
if(node == null) {
return true;
}
if(low != null && node.val <= low) return false;
if(high != null && node.val >= high) return false;
return dfs(node.left,low,node.val) && dfs(node.right,node.val,high);
}
}
As you see , initially we set the lower and upper bounds to null instead of infinity.
null value servers well for our purpose there.
We will ignore the bound check if the value is null .
Else you compare the lower and upper bound for the current node.
And then for the left sub tree you set the lower bound to the same lower bound value of the current node
and you set the upper bound to the current node value.
You validate the left subtree recursively this way.
Similarly.
For the right sub tree,
You set the lower bound to the current node value.
And you set the upper bound to the same upper bound value of the current node.
You validate the right subtree recursively.
The base condition for the recursive call is to check for null.
If it is null then we have reached the end of the tree without any validation error ,so return true.
Time complexity:
We traverse through each node so time complexity is O(n)
Space complexity:
We need memory for each recursive call , so in the worst case the space complexity is O(n)
Approach 2 – Using BFS
Instead of Depth First Search, you can use Breadth First Search as well.
In this case, you will use a queue instead of recursion.
At each stage of the traversal , you will push the lower and upper bound values into separate queues.
You will also push the current node into a separate queue.
You will pop the current node and its lower and upper bound limits , validate they are within limits and then push the left node and the right nodes of the current node and their respective limits to the respective queues.
You continue the validation as before until all the nodes are processed /the queue becomes empty.
Here is the code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
if(root == null ) return true;
Integer low = null;
Integer high = null;
//three queues for storing the node and their lower and upper limits
Queue<TreeNode> bstQueue = new LinkedList<TreeNode>();
Queue<Integer> lowValues = new LinkedList<Integer>();
Queue<Integer> highValues = new LinkedList<Integer>();
bstQueue.add(root);
lowValues.add(low);
highValues.add(high);
while(!bstQueue.isEmpty()){
TreeNode node = bstQueue.poll();
Integer l = lowValues.poll();
Integer h = highValues.poll();
//check the next node if current node is null
if(node == null) continue;
//bound check
if(l!=null && node.val <= l) return false;
if(h!=null && node.val >= h) return false;
//push left node and its limits
bstQueue.add(node.left);
lowValues.add(l);
highValues.add(node.val);
//push right node and its limits
bstQueue.add(node.right);
lowValues.add(node.val);
highValues.add(h);
}
return true;
}
}
The bound check is the same as in the Depth First Search:
you check if the current node is within the lower and upper limits.
And then for the left sub tree,
You set the lower bound to the current lower bound value.
You set the upper bound to the current node value.
And then for the right sub tree,
You set the lower bound to the current node value.
You set the upper bound to the current higher bound value.
Time complexity and Space complexity remain the same as before.
We use 3 queues though so space complexity is O(3n) , removing the constant it is O(n)
Approach 3 – Inorder Traversal:
In this approach you do inorder traversal of a tree.
In Inorder traversal , the natural order is maintained.
That is if you do inorder traversal of a tree and read its values from left to right , they will be sorted if it is a binary search tree.
So the logic used here is:
At each stage of inorder traversal , check if the current value is greater than the previous value.
To do this,
you need a variable to store the previous value.
And you recursively do inorder traversal : Left -> current -> Right direction.
Here is the code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
Integer previous;
public boolean isValidBST(TreeNode root) {
return inorder(root);
}
public boolean inorder(TreeNode node){
if(node == null) {
return true;
}
if(!inorder(node.left)) return false;
if(previous != null && node.val <= previous) return false;
previous = node.val;
return inorder(node.right);
}
}
Algorithm for inorder traversal:
- Check if current node is null , if so return true
- Do inorder traversal for the left sub tree recursively and return false if it is invalid
- Check if current value is greater than previous value else return false
- Assign current node value to the previous value to be used for the next check.
- Do inorder traversal for the right subtree recursively and return the result
Time complexity and Space complexity remain the same as before
Approach 4 – Iterative Inorder Traversal
In this case , instead of recursion we use a stack for the inorder traversal.
Create a stack to store the nodes.
Algorithm:
Go to the left most node in the tree by pushing all the nodes in the left path of the tree from the root node (current node) to the stack.
Once you reach the bottommost left node,
Pop the top node from the stack (bottom most left node in the tree), compare it with the previous value ,return false if it is greater or equal to current node value.
Assign the current node value to the previous value for the next check.
Go the right node of current node and continue the above process.
Here is the code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
Integer previous = null;
Stack<TreeNode> stack = new Stack<TreeNode>();
// do traversal until stack is empty or the root node is null
while(!stack.isEmpty() || root != null){
//this while loop makes sure you reach the left most node and push all the nodes in the path to the stack
while(root != null){
stack.add(root);
root = root.left;
}
//pop the left most node
root = stack.pop();
//check with previous value (initially null)
if(previous != null && root.val <=previous) return false;
//prepare for next check
previous = root.val;
//move to the right node to continue the validation.
root = root.right;
}
return true;
}
}
Time complexity and space complexity remain the same O(n)
That’s it!
Leave a Reply