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

Method 0 - Recursive but Wrong

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

graph TD;
A(3) --- B(2) & C(5)
B --- D(1) & E(4)
style E fill:orange

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

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.

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

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;
	}
}
 
1
2
3
4
5
6
7

int minValue(TreeNode root) {
	TreeNode current = root; // loop down to find the leftmost leaf
	while (current.left != null) {
		current = current.left;
	}
	return (current.val);
}
1
2
3
4
5
6
7

int maxValue(TreeNode root) {
	TreeNode current = root; // loop down to find the leftmost leaf
	while (current.right != null) {
		current = current.right;
	}
	return (current.val);
}

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

class Solution {

	public boolean isValidBST(TreeNode root) {
		return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
	}

	// 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, long min, long max) {
		if (root == null) {
			return true;
		}

		if (root.val <= min && root.val >= max) {
			return false;
		}

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

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;

	}
}

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)
  • 🧺 Space complexity: O(n)

Method 6 - Iterative Solution Using BFS

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

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


	Stack<TreeNode> nodeStack;

	nodeStack.push(root);

	while (!nodeStack.empty()) {
		TreeNode current = nodeStack.top();

		nodeStack.pop();

		if (current.left != null) {
			nodeStack.push(current.left);
			if (current.left.val > current.val)
				return false;
		}

		if (current.right != null) {
			nodeStack.push(current.right);
			if (current.right.val<current.val)
				return false;
		}
	}

	return true;
}