[Algorithms] 8 - Valid Binary Search Tree

Link for the problem

Link for the solution

This may not be the hardest BST problem, but really good to understand the concept of BST structure.

Wrong Approach

When I first saw the problem, I simply tried to compare the parent node and its left & right nodes with the recursion. I thought it will eventually give me the answer by using recursion, because I am recursively checking all parents are strictly greater than its left and smaller than it right.

Mistake that I made

The mistake I made here (and probably 99% of people who tried to solve this problem would have faced the same issue) was that, I was merely checking if each subtree is valid. It is weird, because it sounds true that if all subtrees in the BST are valid BSTs, than the whole tree is a valid BST. But
look at the following example.

Invalid BST - 3 and 4 cannot be in the right tree of 5


In the example, all subtrees are valid. But the whole BST is not valid. Therefore, we need to do something more to make sure the tree is a valid BST. But what should we do?

Solution

Let's start from why checking all subtrees are valid does not lead to the answer. The reason is that, for each check we do not consider the previous results. Then what previous results that we need to keep track of? The minimum and the maximum boundaries.

For example,

      (10)
     /    \
   (7)    (17)
   /\      /\
 (4)(9)  (11)(18)
    /\
  (1)(?)

Let's think of the value that we can fill in (?).
=> [10,11,12,13... ]
Because we can tell the value should be strictly bigger than 9

But if we consider that fact that all (?) has to be smaller than 10, because (?) in the left side of the root node with the value of 10, then we can find out that there is no number we can fill in the blank.

Okay now it seems clearer, but we need to figure one more thing. When do we get the maximum boundary?

Let's start from the root node. We can see that every node inside of the root node's left tree has to be smaller than 10. So everything under 10's left node will be having the maximum boundary of 10. On the other hand, every node inside of the root node's right tree has to be greater than 10.

left tree nodes => [...8,9]
right tree nodes => [11, 12, ...]

Therefore, we can see that every time we move to left child, the maximum boundary will be set and every time we move to the right child, the minimum boundary will be set.

My solution

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        // The idea for the solution:
        //      Need to set the minimum and maximum boundary
        //      1. Left node cannot be greater than the current node
        //      2. Right node cannot be smaller than the current node
        //      3. If the node is left, maximum boundary will be set up.
        //      4. If the node is right, minimum boundary will be set up.
        return helper(root, LONG_MIN, LONG_MAX);
    }

    bool helper(TreeNode* root, long long int minVal, long long int maxVal){

        // Base case
        if(!root)return true;

        // within the range of minval and maxval
        if(root->val <= minVal || root->val >= maxVal)return false;

        // root->left => should be less than root->val
        if(root->left && root->left->val >= root->val) return false;

        // root->right => should be greater than root->val
        if(root->right && root->right->val <= root->val) return false;

        // Should update the left node restriction
        return (helper(root->left, minVal, root->val) && helper(root->right, root->val, maxVal));
    }
};