Problem

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

Assume a 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.

Examples

Example 1:

1
2
3

  5   
 / \
2   7

1
2

Input: root = [5,2,7]
Output: true

Example 2:

1
2
3

  5   
 / \
6   7

1
2
3

Input: root = [5,6,7]
Output: false
Explanation: because the 6 is not ok to the left of the 5

Example 3:

1
2
3
4
5

    5 
   / \
  2   7
 /
1

1
2

Input: root = [5,2,7,1]
Output: true

Example 4:

1
2
3
4
5

    5 
   / \
  2   7
 / \
1   6

1
2
3

Input: root = [5,2,7,1,6]
Output: false
Explanation: the 6 is ok with the 2, but the 6 is not ok with the 5

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 0 - Recursive but Wrong

Intuition

A common first thought is to directly translate the BST definition into a simple recursive check. The definition states that a node’s value must be greater than its left child’s value and smaller than its right child’s value. This leads to an intuitive check at each node.

Approach

For each node in the tree, we recursively check if node.val is greater than node.left.val and less than node.right.val. While this seems correct, it’s a flawed approach. It only validates a node against its immediate children, failing to enforce the constraint against all ancestor nodes. For example, a node might be a valid child of its parent but still be in the wrong place relative to its grandparent, violating the overall BST structure.

Here is the test case which shows it fails, where 4 should be on the left of node root node 5.

graph TD
    A(5) --> B(1);
    A(5) --> C(7);
    C(7) --> D(4);
    C(7) --> E(8);
    style D fill:#ffcccc,stroke:#cc0000,stroke-width:2px
    linkStyle 0 stroke-width:4px,stroke:grey
    linkStyle 1 stroke-width:4px,stroke:grey
    linkStyle 2 stroke-width:4px,stroke:grey
    linkStyle 3 stroke-width:4px,stroke:grey

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

boolean isValidBST(TreeNode root) {
	if (root == null) {
		return true;
	}

	// false if left is > than root
	if (root.left != null && root.left.val > root.val) {
		return false;
	}

	// false if right is<than root
	if (root.right != null && root.right.val<root.val) {
		return false;
	}

	// false if, recursively, the left or right is not a BST
	if (!isValidBST(root.left) || !isValidBST(root.right)) {
		return false;
	}

	// passing all that, it's a BST
	return true;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        # Flawed check: false if left child is > than root
        if root.left and root.left.val > root.val:
            return False

        # Flawed check: false if right child is < than root
        if root.right and root.right.val < root.val:
            return False

        # Recursively apply the same flawed logic
        if not self.isValidBST(root.left) or not self.isValidBST(root.right):
            return False

        return True

Method 1 - Recursive but Inefficient - Max Value and Min Value for Each Node

Intuition

To fix the flaw in the first approach, we need to ensure that for any given node, all nodes in its left subtree are smaller and all nodes in its right subtree are larger. This suggests a more thorough validation at each step.

Approach

For each node, check if max value in left subtree is smaller than the node and min value in right subtree greater than the node.

For each node n in the tree, we can perform two separate traversals:

  1. Traverse the entire left subtree of n to confirm every node’s value is less than n.val.
  2. Traverse the entire right subtree of n to confirm every node’s value is greater than n.val.

We do this for every single node in the main tree. This is guaranteed to be correct because it rigorously checks the global BST property for each node.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class Solution {
	public int isValidBST(TreeNode root) {
		if (root == null)
			return true;

		/* false if the max of the left is > than us */
		if (root.left != null && maxValue(root.left) > root.val) {
			return false;
		}

		/* false if the min of the right is <= than us */
		if (root.right != null && minValue(root.right) < root.val) {
			return false;
		}

		/* false if, recursively, the left or right is not a BST */
		if (!isValidBST(root.left) || !isValidBST(root.right)) {
			return false;
		}

		/* passing all that, it's a BST */
		return true;
	}
	
	// It is assumed that you have helper functions `minValue()` and `maxValue()` that return the min or max int value from a non-empty tree.
	private int minValue(TreeNode root) {
		TreeNode current = root; // loop down to find the leftmost leaf
		while (current.left != null) {
			current = current.left;
		}
		return (current.val);
	}
	
	private int maxValue(TreeNode root) {
		TreeNode current = root; // loop down to find the leftmost leaf
		while (current.right != null) {
			current = current.right;
		}
		return (current.val);
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        # Helper to find the maximum value in an entire subtree
        def max_value(node: Optional[TreeNode]) -> float:
            if not node:
                return float('-inf')
            return max(node.val, max_value(node.left), max_value(node.right))

        # Helper to find the minimum value in an entire subtree
        def min_value(node: Optional[TreeNode]) -> float:
            if not node:
                return float('inf')
            return min(node.val, min_value(node.left), min_value(node.right))

        # 1. False if the max of the left subtree is >= current node's value
        if root.left and max_value(root.left) >= root.val:
            return False

        # 2. False if the min of the right subtree is <= current node's value
        if root.right and min_value(root.right) <= root.val:
            return False

        # 3. False if, recursively, the left or right subtree is not a valid BST
        if not self.isValidBST(root.left) or not self.isValidBST(root.right):
            return False

        # If all checks pass, it's a valid BST at this node
        return True

Complexity

  • ⏰ Time complexity: O(n^2) - O(n) time to traverse nodes, and O(n) time find min and value for each node.
  • 🧺 Space complexity: O(n), for stack space in recursion

Method 3 - Recursive but Efficient way 🏆

All values in the left subtree must be less than the root, and all values in the right subtree must be greater than the root. Therefore, we check each node’s value against these boundaries. This method traverses the left subtree first. If a violation occurs near the root but on the right subtree, the time complexity remains O(n). However, the second solution below can detect violations near the root more quickly.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public boolean isValidBST(TreeNode root) {
        // Initialize with the full range of long values.
        return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean isValid(TreeNode node, long min, long max) {
        if (node == null) {
            return true;
        }

        // Check if the current node's value is within the valid range.
        if (node.val <= min || node.val >= max) {
            return false;
        }

        // Recursively check the left and right subtrees with updated bounds.
        // For the left child, the parent's value is the new max.
        // For the right child, the parent's value is the new min.
        return isValid(node.left, min, node.val) && isValid(node.right, node.val, max);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {

	public boolean isValidBST(TreeNode root) {
		return helper(root, null, null);
	}

	// We are using long min and long max to handle the case
	// when node's value is Integer.MIN_VALUE OR Integer.MAX_VALUE
	private boolean helper(TreeNode root, Integer min, Integer max) {
		if (root == null) {
			return true;
		}

		return (min == null || root.val > min) && (max == null || root.val  <  max) &&
			helper(root.left, min, root.val) &&
			helper(root.right, root.val, max);

	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {

	public boolean isValidBST(TreeNode root) {
		return helper(root, null, null);
	}

	// We are using long min and long max to handle the case
	// when node's value is Integer.MIN_VALUE OR Integer.MAX_VALUE
	private boolean helper(TreeNode root, TreeNode min, TreeNode max) {
		if (root == null) {
			return true;
		}

		return (min == null || root.val > min.val) && (max == null || root.val  <  max.val) &&
			helper(root.left, min, root) &&
			helper(root.right, root, max);
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def is_valid(node, min_val, max_val):
            if not node:
                return True
            
            if not (min_val < node.val < max_val):
                return False
            
            return is_valid(node.left, min_val, node.val) and \
                   is_valid(node.right, node.val, max_val)

        return is_valid(root, float('-inf'), float('inf'))

Complexity

  • ⏰ Time complexity: O(n), because we visit each node exactly once.
  • 🧺 Space complexity: O(n) for the recursion stack in the worst case of a completely unbalanced tree.

Method 4 - Iterative Using Queue and Node Modification

We can create a new BTNode with long left and right values, denoting the smallest value on the left and max value on right. Each time, we add value to queue, we set the min and max we have seen so far, and when we poll out the values should be in the range [left, right].

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

 //define a BNode class with TreeNode and it's boundaries
 class BNode {
 	TreeNode n;
 	long left;
 	long right;
 	public BNode(TreeNode n, long left, long right) {
 		this.n = n;
 		this.left = left;
 		this.right = right;
 	}
 }

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {

	public boolean isValidBST(TreeNode root) {
		if (root == null)
			return true;

		LinkedList<BNode> queue = new LinkedList<BNode>();
		queue.add(new BNode(root, Long.MIN_VALUE, Long.MAX_VALUE));

		while (!queue.isEmpty()) {
			BNode b = queue.poll();

			if (b.n.val <= b.left || b.n.val >= b.right) {
				return false;
			}

			if (b.n.left != null) {
				queue.offer(new BNode(b.n.left, b.left, b.n.val));
			}

			if (b.n.right != null) {
				queue.offer(new BNode(b.n.right, b.n.val, b.right));
			}
		}

		return true;

	}
}

Complexity

  • ⏰ Time complexity: O(n), as each node in the tree is visited exactly once.
  • 🧺 Space complexity: O(n) in the worst case, because the queue will have to store all nodes at the widest level of the tree, which can be up to n/2 nodes for a complete tree.

Method 5 - Inorder Traversal (with and without Aux array)

Read more about Binary Tree Inorder Traversal.

Here are the steps to follow:

  1. Perform an in-order traversal of the tree and store the results in a temporary array.
  2. Verify if the temporary array is sorted in ascending order; if so, the tree is a BST.

To avoid using an auxiliary array, we can track the previously visited node during the in-order traversal. If the current node’s value is less than the previous node’s value, the tree is not a BST.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
	TreeNode prev = null;
	public boolean isValidBST(TreeNode root) {
		// traverse the tree in inorder fashion and keep track of prev node
		if (root!=null) {
			if (!isValidBST(root.left))
				return false;
	
			// Allows only distinct valued nodes
			if (prev != null && root.val<= prev.val) {
			
				return false;
				}
	
			prev = root;
	
			return isValidBST(root.right);
		}
	
		return true;
	}
}

Complexity

  • ⏰ Time complexity: O(n) as it traverses each node once
  • 🧺 Space complexity: O(n) in the worst case due to the depth of the recursion stack.

Method 6 - Iterative Solution Using DFS

Similar to recursive DFS, we can also perform iterative DFS using stack.

The below code is just a modified version of the standard non-recursive Breadth First Search (BFS) of a binary tree. If you are unfamiliar with the algorithm for BFS, you can find Binary Tree Level Order Traversal.

To check if each node adheres to the rules of a binary search tree (BST), we verify that each left child’s value is less than the current node’s value and each right child’s value is greater. A binary tree is considered a BST if all nodes satisfy these conditions. If all nodes are validated without any violations, we return true; otherwise, we return false upon detecting a single violation.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class Solution {
    // Helper class to store a node and its valid range
    private static class NodeState {
        public TreeNode node;
        public Long min;
        public Long max;

        public NodeState(TreeNode node, Long min, Long max) {
            this.node = node;
            this.min = min;
            this.max = max;
        }
    }

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        // Use a stack for iterative DFS
        Stack<NodeState> stack = new Stack<>();
        
        // Start with the root node. It has no restrictions, so we use null 
        // for min and max to represent negative and positive infinity.
        stack.push(new NodeState(root, null, null));

        while (!stack.isEmpty()) {
            NodeState current = stack.pop();
            
            // Check if the node's value is outside its allowed range
            if (current.min != null && current.node.val <= current.min) {
                return false;
            }
            if (current.max != null && current.node.val >= current.max) {
                return false;
            }

            // If the right child exists, push it to the stack with an updated min bound.
            // Its new min is its parent's value.
            if (current.node.right != null) {
                stack.push(new NodeState(current.node.right, (long) current.node.val, current.max));
            }
            
            // If the left child exists, push it to the stack with an updated max bound.
            // Its new max is its parent's value.
            if (current.node.left != null) {
                stack.push(new NodeState(current.node.left, current.min, (long) current.node.val));
            }
        }

        // If we traverse the whole tree without finding an invalid node, it's a valid BST.
        return true;
    }
}

Complexity

  • ⏰ Time complexity: O(n) as every node is pushed and popped once
  • 🧺 Space complexity: O(n) in the worst case, determined by the maximum depth of the stack for a skewed tree.