Validate Binary Search Tree (BST)

Difficulty: Easy, Asked-in: Microsoft, Google, Amazon, eBay, Adobe, Qualcomm, VMWare, Walmart.

Key takeaway: An excellent problem to understand the properties of binary search trees and learn step-by-step optimization using various approaches.

Let’s understand the problem

Given the root of a binary tree, write a program to check whether it is a valid Binary Search Tree (BST) or not. A BST is valid if it has the following properties:

• All nodes in the left subtree have values less than the root node's value.
• All nodes in the right subtree have values greater than the root node's value.
• Both the left and right subtrees are also binary search trees.

This is known as the BST property, which must hold true for each node in the tree, if it is a valid BST.

Examples

Discussed solution approaches

• A wrong solution approach!
• Brute force approach by checking BST property at each node
• Optimized version of the brute force approach
• Using inorder traversal and extra space
• In-place solution using inorder traversal

Wrong solution approach!

A poor understanding of this problem can lead to a wrong approach. For example, suppose we understood the BST property incorrectly and designed this solution: We visit each node recursively and compare value stored in each node with value stored on the left and right child. If the node value is less than left child value or greater than right child value, we return false. Otherwise, we recursively call the same function to verify BST for left and right sub-tree.

Pseudocode

bool isValidBST (TreeNode root)
{
    if (root == NULL)
        return true 
    
    if (root->left != NULL && root->left->value > root->value)
        return false 
    
    if (root->right != NULL && root->right->value < root->value)
        return false
        
    bool left = isValidBST(root->left)
    bool right = isValidBST(root->right) 
    
    if(left == true && right == true)
        return true
    else 
        return false
}

What is the mistake in above solution?

Based on the BST property, each node value must be greater than all nodes in the left sub-tree and less than all nodes in the right sub-tree. But above solution check this only for the children of each node, not the entire left or right subtree. So this solution will give the wrong result for several input cases. Consider this example:

Brute force approach by checking BST property at each node

Solution idea

Now the critical question is: How can we fix the above solution? Here is an idea: A tree can not be BST if left subtree of a node contains any value greater than node’s value and right subtree contains any value smaller than node’s value. In other words, node value must be greater than the maximum in left subtree and less than the minimum in right subtree. Note: In a BST, the rightmost node would be the node with the maximum value and the leftmost node would be the node with the minimum value.

Solution steps

• Base case: If (root == NULL ), return true.
• We find max in the left subtree and min in the right subtree using two helper functions i.e. leftMax = bstMax(root->left) and rightMax = bstMin(root->right).
• If leftMax > root->value or rightMax < root->value, then root node violates the BST property and we return false. Otherwise, root node satisfies the BST property. So we recursively check that left and right subtree are correct BST or not. For this, we call the same function with root->left and root->right as input parameters.

bool left = isValidBST(root->left)
bool right = isValidBST(root->right)

• If both left and right are true, return true. Otherwise, return false.

Solution pseudocode

bool isValidBST(TreeNode root)
{
    if (root == NULL)
        return true
        
    int leftMax = bstMax(root->left)
    int rightMax = bstMin(root->right)
    
    if (leftMax > root->value || rightMax < root->value)
        return false
        
    bool left = isValidBST(root->left)
    bool right = isValidBST(root->right)
    
    if(left == true && right == true)
        return true
    else 
        return false
}

int bstMax(TreeNode root)
{
    while(root->right != NULL)
        root = root->right
    
    return root->value
}

int bstMin(TreeNode root)
{
    while(root->left != NULL)
        root = root->left
    
    return root->value
}

Time complexity analysis

We visit each node recursively, finding the maximum in the left subtree and the minimum in the right subtree by calling bstMax(root->left) and bstMin(root->right). Here, finding the maximum and minimum in the BST are two critical extra operations, and the complexity of these operations depends on the tree structure.

• The worst-case time complexity of finding max and min in a BST = O(n). This is the situation when the tree is highly unbalanced i.e., either left-skewed (all nodes have a left child except the single leaf node) or a right-skewed tree (all nodes have a right child except the single leaf node).
• The recurrence relation for the worst case => T(n) = T(n - 1) + O(n). So worst-case time complexity = O(n^2).
• The best-case time complexity of finding max and min in a BST = O(logn). This is the situation of the completely balanced tree.
• The recurrence relation for the best case => T(n) = 2T(n/2) + O(logn). Proof that the best case time complexity is O(n)! Hint: Use the first case of the master theorem.

An optimized version of the brute force approach

Can we think of solving this problem efficiently? If we observe, we are performing O(n) extra operations for each node in the worst case and because of this, our worst-case time complexity is O(n^2). Now the critical question: Can we optimize the cost of extra operation to O(1)? Let's think!

Solution idea

In a BST, the values stored in the subtree rooted at any node lie within a specific range. In other words, there is an upper (rangeMax) and a lower (rangeMin) limit for the values in a particular subtree. For example:

• The tree with the root node has values in the range (INTMIN, INTMAX).
• The values in the left subtree are within the range (INT_MIN, root->value).
• The values in the right subtree are within the range (root->value, INT_MAX), and so on.

One possible solution is to traverse each node recursively and keep track of the minimum and maximum range of values allowed for the subtree rooted at each node. To do this, we can pass the range values as function arguments while recursing through the left and right subtrees. The initial values for the minimum and maximum range should be INTMIN and INTMAX, respectively.

During this process, if node->value < rangeMin or node->value > rangeMax, then the node’s value falls outside the valid range and violates the BST property. In that case, we return false. Otherwise, we recursively validate the left and right subtrees with updated ranges.

Solution pseudocode

bool isBST(TreeNode root)
{
    return isValidBST(root, INT_MIN, INT_MAX))
}

bool isValidBST(TreeNode root, int rangeMin, int rangeMax)
{
    if(root == NULL)
        return true
    
    if (root->value < rangeMin || root->value > rangeMax)
        return false
        
    bool left = isValidBST(root->left, rangeMin, root->value)
    bool right = isValidBST(root->right, root->value, rangeMax) 
    
    if(left == true && right == true)
        return true
    else 
        return false
}

Time and space complexity analysis

We visit each node only once and perform O(1) operation with each node. So time complexity = n* O(1) = O(n). Space complexity depends on the size of the recursion call stack, which is equal to the height of the tree. So space complexity = O(h). What would be the worst and best case of space complexity? Think!

Using inorder traversal and extra space

Solution idea

As we know, the inorder traversal of a binary search tree visits node values in sorted order. So, another idea would be to traverse the tree using inorder traversal and store the node values in extra memory. Then, we can traverse this extra memory using a loop to check whether the values are sorted. If they are sorted, then the tree is a BST. Otherwise, it is not.

Solution pseudocode

bool isValidBST (TreeNode root)
{
    vector<int> sorted
    inorderTraversal(root, &sorted)
    
    for(int i = 1; i < sorted.size(); i = i + 1)
    {
        if (sorted[i] < sorted[i - 1])
            return false 
    }
    
    return true
}
void inorderTraversal(TreeNode root, int & sorted)
{
    if (root == NULL)
        return
        
    inorderTraversal(root->left, sorted)
    sorted.push(root->value)
    inorderTraversal(root->right, sorted)
}

Time and space complexity analysis

Time complexity = Time complexity of inorder traversal + Time complexity of the single loop to check sorted array = O(n) + O(n) = O(n). Space complexity = O(n) for storing elements in an array + O(h) for recursion stack space = O(n + h).

In-place solution using inorder traversal

Solution idea

The critical question is: Can we think to optimize the above approach and avoid using extra space? As we know that inorder traversal of a BST returns the nodes in sorted order. So one idea would be to keep track of previously visited nodes while traversing the tree. If current node value is less than previous node value, then tree is not BST.

Solution pseudocode: Recursive inorder traversal

bool isBST(TreeNode root)
{
    TreeNode prev = NULL
    return isValidBST(root, &prev)
}

bool isValidBST(TreeNode root, TreeNode &prev) 
{
    if (root == NULL) 
        return true
        
    bool left = isValidBST(root->left, prev)
    
    if (prev != NULL && root->value < prev->value) 
        return false
        
    prev = root
    
    bool right = isValidBST(root->right, prev)
    
    if(left == true && right == true)
        return true
    else 
        return false
}

Solution pseudocode: Iterative inorder traversal using stack

bool isValidBST(TreeNode root) 
{
    if (root == NULL) 
        return true
        
    Stack<TreeNode> stack
    TreeNode curr = root
    TreeNode prev = NULL
    
    while (curr != NULL || stack.isEmpty()== false) 
    {
        if (curr != NULL) 
        {
            stack.push(curr)
            curr = curr->left
        }
        else
        {
            curr = stack.pop()
            if(prev != NULL && curr->value < prev->data) 
                return false
            prev = curr
            curr = curr->right
        }
    }
    
    return true
}

Time and space complexity analysis

We visit each node only once and perform O(1) operation with each node. So time Complexity = n* O(1) = O(n). Space complexity depends on the depth of the size of the recursion call stack, which is equal to the height of the tree. So space complexity = O(h).

Critical Ideas to think!

• In the 4th approach using recursive inorder traversal, can we think of implementing without using the pointer by reference?
• Can we think of implementing 2nd approach, using pointers by reference instead of passing the value?
• Is there a way to solve this problem using some other approach?

Suggested problems to practice

• Check if the given binary tree is a strict binary tree or not
• Check whether the given binary is perfect or not
• Check if a binary tree is a complete tree or not
• Check if a binary tree is a subtree of another binary subtree
• Check if the given binary tree is Heap or not
• Check if the given binary tree is SumTree or not

Please write in the message below if you have alternative approaches or find an error/bug in the above approaches. Enjoy learning, Enjoy algorithms!