Validate Binary Search Tree -LeetCode-Amazon Interview Question

Problem Description can be found here:

Please do not reach-out your white board to draw a recursion tree! Usually it is advised to visualize recursion problem through drawing it.But…

Instead, think about how to think of recursion ? Analyze what thought process is missing ? Without understanding recursion you will not be able to understand how this problem is being solved.

When thinking of solving the recursion problems , I personally find it helpful by thinking in words. Drawing images and visualizing the flow of recursion can help initially, but over time you have to start thinking in terms of Mathematical induction. Please watch MIT Professor Eric Grimson’s video on recursion to really understand how to think of recursion.

So, what do I mean by thinking in words ?

I will let you know when I use it in the explanation, be patient 😉.

Following are the requirements for a valid BST, let us analyze them one by one:

1. The left subtree of a node contains only nodes with keys less than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. Both the left and right subtrees must also be binary search trees.

As soon as you see the first and second requirement you might be tempted into writing the following code as you might analyze the problem superficially and have become the victim of jumping into solution:

if (root->left && ((root->left->val) >= (root->val)) ) {
return false;
}
if (root->right && ((root->right->val) <= (root->val))){
return false;
}

Until you fail at this test case: [5,4,6,null,null,3,7]. You realize that you had made an assumption in understanding the question. I did assume that it can be a BST as long as left and right subtrees are BST and if the node’s left child is smaller than the parent and the node’s right child is greater than the parent. Above example follows all of my assumptions. However, It fails one condition .The right subtree consists of the node value 3 which is smaller than the key(root node’s value) i.e 5 even though the right subtree is a valid BST.

If you re-read the question you will understand that every node value in the left subtree must be smaller than the node’s key and every node value in the right subtree must be bigger than the node’s key. Above code does not take that into consideration. Above code does not compare every single value of a tree to ensure that all the values in left subtree are smaller that the parent’s node value and all the values in the right subtree are greater than the parent’s node value.

The correct and concrete resolution is as follows:

if (root->right && (root->val >= findMin(root->right))){
return false;
}

Where findMin is the helper function that calculates the minimum value of a tree.

if (root->left && (root->val <= findMax(root->left))){
return false;
}

Where findMax is the helper function that calculates the maximum value of a tree.

Finally, let us take care of the final requirement.

As soon as you see the third statement , thinking in words will help again, this will allow you to know exactly what to return at the end of the function i.e .

“Both the left and right subtrees must also be binary search trees”

translates to => return isValidBST(root->left) && isValidBST(root->right);

So then, how to check if those subtrees are BST ?- we already answered it !

Same logic that we used for root node as above except for the subtree you will have a new parent nodes that are left or right child nodes of a root node, recursion basically.

Next, the main decision point is what do you do when you reach the leaf, also base cases for recursion.

Base cases:

1. When there is no node, return false because it automatically qualifies being a BST
2. When there is a node and it has no left and no right subtree, return true, because having just one node also qualifies for being a BST

Recursive cases:

The above written code for requirement 1 and 2 for being a BST will be our recursive cases as it ensures that we have left subtree and the right subtree.

So far we resolved the parts, now let us put the parts together to finally pass all of our test cases and get the desired result:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
     
        if(!root){
            return true;
        }
        if(root && !(root->left) && !(root->right) ){
            return true;
        }
      
        if (root->right && (root->val >= findMin(root->right))){
            return false;
        }
        if (root->left && (root->val <= findMax(root->left))){
            return false;
        }
        
        return isValidBST(root->left) && isValidBST(root->right);
        
    }
    
    int findMin(TreeNode* root){
        if(!root){
            return 2147483647;//Maximum possible value for an int 
        }
        else if(root && !(root->left) && !(root->right) ){
           return root->val;
        }

        return min(root->val,min(findMin(root->left) , findMin(root->right)));
        
    }
        
        
    
    int findMax(TreeNode* root){
         if(!root){
            return -2147483648;//Minimum possible value for an int
        }
        else if(root && !(root->left) && !(root->right) ){
            return root->val;
        }
        return max(root->val,max(findMax(root->left) , findMax(root->right)));
        
    }
    
    
};

Done ! Take a break now :)

And The runtime of my implementation beats 99.38% of cpp submissions.

Would highly appreciate your feedback if you find anything hard to understand so that I can improve my technical writing !