This article is the first one in the Random DS/Algo series. The purpose of this series is to just act as random collection of DS/Algo problems I solved so that in future I might revisit what I explained to people on the Internet 🤷♂️.
This is one those questions that I always practice before an interview.
The leetcode problem statement goes like this :-
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.
There are 3 implementations that I know which can help us validate a BST.
One of the clean features of a BST is that if you do an inorder traversal of the same, you get the node values in a sorted order.
function isValidBST(root){
const arr = [];
helper(root,arr);
for(let index = 0;index<arr.length-1;index++){
if(arr[index+1]<=arr[index]){
return false;
}
}
return true;
}
function helper(root,arr){
if(!root)
return;
helper(root.left,arr);
arr.push(root.val);
helper(root.right,arr);
}
Approach breakdown :-
Initialize an empty array arr.
Call helper(root,arr) which internally does :-
Traverse the BST in inorder fashion.
Push each root.val inside the arr.
Then we loop over the arr and for any index if an element is less than or equal to previous element, then we simply return false. This is because elements should have been strictly increasing as per the requirements.
Otherwise, we return true.
It's possible to do the above and exit early if there is an invalid BST without using extra arr space.
var isValidBST = function(root){
const prev = helper(root,null);
return prev.isNotValid ? false : true;
}
function helper(root,prev){
if(!root)
return prev;
prev = helper(root.left,prev);
if(prev && root.val <= prev.val){
prev.isNotValid = true;
}
if(prev?.isNotValid)
return prev;
prev = root;
prev = helper(root.right,prev);
return prev;
}
Approach breakdown :-
Let's consider helper(root,prev) first (prev represents previous node) :-
if(!root) return prev - If the root is undefined , we return the prev element.
prev = helper(root.left,prev) - We will first go through the left subtree for each root to find the prev element.
if(prev && root.val <= prev.val){ prev.isNotValid = true; } - Once we return from the left subtree , if prev exists, we compare root.val and prev.val to check if current root.val is less than or equal to prev.val. If it is, we create a property on prev by the name of isNotValid and set it to true.
if(prev?.isNotValid) return prev; - Next we check if this prev.isNotValid exists or not and if it does then we simply return prev to exit early and not further proceed for subsequent right subtree.
prev = root - This is how we set the prev value to root so that for next node we can use this prev value for necessary comparisons.
prev = helper(root.right,prev); - Going through the right subtree for each root to find the prev element.
return prev; - It's essential to return the prev to the calling function for value to reflect.
const prev = helper(root,null); - Inside isValidBST, we get the prev element from helper(root,null).
return prev.isNotValid ? false : true; - If prev.isNotValid exists then that means the BST is invalid and we return false else we return true.
Utilizing the BST property
In BST we can say that each node value will be more than it's left ancestor and less than it's right ancestor for it to be valid. This is what we are going to use now :-
var isValidBST = function(root){
return helper(root,-Infinity,Infinity);
}
function helper(root,leftMax,rightMax){
if(!root)
return true;
if(root.val > leftMax && root.val < rightMax) {
return helper(root.left,leftMax,root.val) && helper(root.right,root.val,rightMax);
}
return false;
}
Approach breakdown :-
Let's consider helper(root,prev):-
if(!root) return true; - If the root is undefined we can say that the BST is valid till now.
if(root.val > leftMax && root.val < rightMax) { return helper(root.left,leftMax,root.val) && helper(root.right,root.val,rightMax); } - This is the core logic where we compare root.val with leftMax and rightMax. Only if root.val is greater than leftMax and root.val is less than rightMax, we can proceed further to check for corresponding left subtree and right subtree and it's required that both of the subtrees need to return true for the BST to be valid. In case of left subtree, rightMax will change to current root.val and in case of right subtree, leftMax will change to current root.val.
If the above condition fails, then we know it's not further required to check for any subsequent left or right subtree and simply return false.
Inside isValidBST, we do return helper(root,-Infinity,Infinity); and pass leftMax as -Infinity and rightMax as Infinity as initial values for our root node.
Out of all the approaches the last one is really clean and I guess an interviewer might expect it. I have given interviews where the first approach was enough and interviewer didn't ask for any optimizations. But if they do, I might skip the second one and jump straight to the third one.
Also I have ignored the space taken by call stack due to recursion and well you never know I might update this article in the future with more approaches if i feel so
Thank you for your time :D
