Last updated on March 2nd, 2025 at 07:15 pm

Here, we see a Validate Binary Search Tree LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Depth-First Search, Tree

Companies

Amazon, Bloomberg, Facebook, Microsoft

Level of Question

Medium

Validate Binary Search Tree LeetCode Solution

1. Problem Statement

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.

Example 1:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Tree Depth First Search (DFS). This pattern is used to traverse the tree recursively or iteratively, exploring as far as possible along each branch before backtracking. The goal is to validate whether the given binary tree satisfies the properties of a Binary Search Tree (BST).

3. Code Implementation in Different Languages

3.1 Validate Binary Search Tree C++

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        if(!isValid(root->left, root->val, true) || !isValid(root->right, root->val, false)) return false;
        return isValidBST(root->left) && isValidBST(root->right);
    }
    
    bool isValid(TreeNode* root, int bound, bool isLeft){
        return !root || (isLeft ? root->val < bound : root->val > bound ) && isValid(root->left, bound, isLeft) && isValid(root->right, bound, isLeft);
    }
};

3.2 Validate Binary Search Tree Java

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);        
    }
}

3.3 Validate Binary Search Tree JavaScript

var isValidBST = function(root) {
    function inOrder(node) {
        if(!node) return [];
        return [...inOrder(node.left), node.val, ...inOrder(node.right)]
    }
    
    const sortedArr = inOrder(root);
    
    for(let i = 0; i < sortedArr.length; i++) {
        if(sortedArr[i+1] <= sortedArr[i]) return false;
    }
    return true;    
};

3.4 Validate Binary Search Tree Python

class Solution(object):
    def isValidBST(self, root):
        stack = [None]
        prev = -float("inf")
        while stack:
            while root:
                stack.append(root)
                root = root.left
            x = stack.pop()
            if x:
                if x.val <= prev:
                    return False
                prev = x.val
                root = x.right
                
        return True

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n)	O(h)
Java	O(n)	O(h)
JavaScript	O(n)	O(n)
Python	O(n)	O(h)

where h is the height of the tree.

• The Java and Python implementations are more efficient in terms of time complexity compared to the C++ implementation.
• The JavaScript implementation uses more space due to the array created during in-order traversal.
• The C++ implementation has a suboptimal time complexity due to redundant subtree traversals in the isValid function.