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:

  5   
 / \
2   7

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

Example 2:

  5   
 / \
6   7

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

Example 3:

    5 
   / \
  2   7
 /
1

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

Example 4:

    5 
   / \
  2   7
 / \
1   6

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

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

Here is the test case which shows it fails, where 4 should be right of root node 3.

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

Java
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.

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

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

Java
Using Long min and max values
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));

}
Using Integer object

We can use Integer object and null pointer to avoid the corner cases (when node has value Integer.MIN_VALUE or Integer.MAX_VALUE ). Also, objects are pass by reference compared to pass by value for longs.

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

	}
}
Using TreeNode object

Since, we are using objects, why not use proper TreeNode object.

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].

 //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

Java
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

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

The use of instance variable or static variable can also be avoided by using reference to prev node as a parameter. Also, we are using calling isValidBST() with right node after setting prev to root as we care about the next node of that root.

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 Problem.

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

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