Validate Binary Search Tree Solution

Validate Binary Search Tree is asked a lot in interview questions now a day. So, Today we will be discussing the algorithm and solution in Python, C++, and JAVA for this question.

Question: Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

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.

Example 1:

Input: root = [1,2,3]
Output: true
Validate Binary Search Tree Solution

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -231 <= Node.val <= 231 - 1

Solution in C++

As you can find this question on LeetCode. To know the solution below is the algorithm used to solve this problem.

Algorithm:

It is really simple to validate the BST if you are aware of Inorder Traversal in BST. As per theory if you perform Inorder traversal on BST then you will receive the tree node values in ascending order. So we will follow the below steps.

  • Perform Inorder Traversal on existing Tree.
  • Store them in a List
  • Now iterate through the list and compare each element is smaller than its descending elements.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void getInorder(TreeNode* root, vector<int> &getElem){
        if(root==NULL) return;
        getInorder(root->left,getElem);
        getElem.push_back(root->val);
        getInorder(root->right,getElem);
    }
    bool isValidBST(TreeNode* root) {
        if(root==NULL) return true;
        vector<int> getElem;
        getInorder(root,getElem);
        for(int i=0;i<getElem.size()-1;i++){
            if(getElem[i]>=getElem[i+1]) return false;
        }
        return true;
    }
};

Solution in Python

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        getList, prev = [], -math.inf
        while getList or root:
            while root:
                getList.append(root)
                root = root.left
            root = getList.pop()
            # If next element in inorder traversal
            # is smaller than the previous one
            # that's not BST.
            if root.val <= prev:
                return False
            prev = root.val
            root = root.right
        return True

Solution in JAVA

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
        if (root == null) return true;
        if (root.val >= maxVal || root.val <= minVal) return false;
        return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
    }
}

Complexity Analysis

  • Time complexity: O(N) in the worst case when the tree is BST or the “bad” element is a rightmost leaf.
  • Space complexity: O(N) to keep stack.
Runtime for validate binary search tree

If you liked the answer then please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.

Wanna read more interview-related questions? Check Top Interview Questions category.

Leave a Comment