☕ DSA Java Articles

Topics › Binary Search Trees › Practice Problems

Check if a tree is a BST or not

Medium TUF ID 100 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the root of a binary tree. Decide whether it is a valid binary search tree (BST). A tree is a valid BST when, at every node:

The empty tree is a valid BST. Constraints (LeetCode version): up to 10^4 nodes, and keys can be any 32-bit signed integer, including Integer.MIN_VALUE and Integer.MAX_VALUE. Duplicate keys make the tree invalid.

Example 1

    2
   / \
  1   3
answer = true        // 1 < 2 < 3

Example 2

      5
     / \
    1   4
       / \
      3   6
answer = false       // 4 is in the right subtree of 5 but smaller than 5

Example 3 (the classic trap)

      5
     / \
    4   6
       / \
      3   7
answer = false       // 3 < 6 is fine locally, but 3 sits in the right subtree of 5

Example 3 is the one to keep in mind. Checking only that each node is larger than its left child and smaller than its right child passes this tree, yet it is not a BST. The rule is about whole subtrees, not about children.

Approach 1: Brute force

Intuition. Translate the definition directly. “Every key in the left subtree is smaller than the node” is the same as “the largest key in the left subtree is smaller than the node”. Likewise for the right side with the smallest key. So at each node, compute the maximum of the left subtree and the minimum of the right subtree, compare, and then recurse into both children. It is correct by definition, but it recomputes the same subtree extremes again and again.

Algorithm.

  1. An empty tree is valid.
  2. If the left child exists and maxOf(left) >= root.val, return false.
  3. If the right child exists and minOf(right) <= root.val, return false.
  4. Otherwise the answer is bruteForce(left) && bruteForce(right).
static boolean bruteForce(TreeNode root) {
    if (root == null) return true;
    if (root.left != null && maxOf(root.left) >= root.val) return false;
    if (root.right != null && minOf(root.right) <= root.val) return false;
    return bruteForce(root.left) && bruteForce(root.right);
}

static int maxOf(TreeNode node) {
    if (node == null) return Integer.MIN_VALUE;
    return Math.max(node.val, Math.max(maxOf(node.left), maxOf(node.right)));
}

static int minOf(TreeNode node) {
    if (node == null) return Integer.MAX_VALUE;
    return Math.min(node.val, Math.min(minOf(node.left), minOf(node.right)));
}

Complexity. Time O(n^2) in the worst case: a node at depth d is scanned by the maxOf/minOf call of each of its d ancestors, so the total work is the sum of all depths. For a chain that is about n^2 / 2; for a balanced tree it is O(n log n). Space O(h) for the recursion, where h is the tree height.

maxOf and minOf return sentinels for an empty subtree, but a sentinel never decides the result: bruteForce calls them only on a non-empty child, and inside them a sentinel is always combined with a real key through Math.max or Math.min. So a real key equal to Integer.MIN_VALUE or Integer.MAX_VALUE is never confused with “empty”.

Approach 2: Better, in-order must be strictly increasing

Intuition. An in-order traversal visits the left subtree, then the node, then the right subtree. In a BST everything on the left is smaller and everything on the right is larger, so in-order lists the keys in sorted order. The converse also holds, and that is what makes this a complete test: if the in-order sequence is strictly increasing, the tree is a BST. For any node, its left subtree occupies a contiguous block of the sequence immediately before it and its right subtree a block immediately after it. A strictly increasing sequence therefore puts every left key below the node and every right key above it.

Algorithm.

  1. Run an in-order traversal and append each key to a list.
  2. Scan the list; if any key is >= the next one, return false.
  3. Otherwise return true.
static boolean better(TreeNode root) {
    List<Integer> inorder = new ArrayList<>();
    collectInorder(root, inorder);
    for (int i = 1; i < inorder.size(); i++) {
        if (inorder.get(i - 1) >= inorder.get(i)) return false;   // equal keys are not allowed either
    }
    return true;
}

static void collectInorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    collectInorder(node.left, out);
    out.add(node.val);
    collectInorder(node.right, out);
}

Complexity. Time O(n): one traversal plus one scan. Space O(n) for the list, plus O(h) for recursion.

You can drop the list by remembering only the previously visited key during the traversal and failing as soon as the current key is not larger. That keeps the time at O(n) and the extra space at O(h). The next approach reaches the same bounds with a cleaner idea that also generalises to other “constraint flows down the tree” problems.

Approach 3: Optimal, pass down the allowed range

Intuition. Instead of asking each node “what is below you?”, tell each node “what range you must fall in”. The root may hold any key, so its range is (-∞, +∞). When we step into the left child of a node with key v, everything there must be below v, so the upper bound tightens to v. When we step right, the lower bound tightens to v. Every ancestor contributes one constraint of the form “below my key” or “above my key”, and only the tightest constraint of each kind matters, so two numbers carry everything the node needs to know.

This is exactly what catches Example 3: key 3 arrives at the left child of 6 with the range (5, 6), inherited from being in the right subtree of 5, and 3 is outside it.

Algorithm.

  1. Call inRange(root, -∞, +∞).
  2. In inRange(node, low, high): an empty node is valid. If node.val <= low or node.val >= high, return false.
  3. Recurse left with (low, node.val) and right with (node.val, high); both must be valid.
static boolean optimal(TreeNode root) {
    return inRange(root, Long.MIN_VALUE, Long.MAX_VALUE);   // long bounds: keys may be Integer.MIN_VALUE / MAX_VALUE
}

static boolean inRange(TreeNode node, long low, long high) {
    if (node == null) return true;
    if (node.val <= low || node.val >= high) return false;
    return inRange(node.left, low, node.val) && inRange(node.right, node.val, high);
}

The bounds are long. If we used Integer.MIN_VALUE and Integer.MAX_VALUE as the infinities, a tree whose root really is Integer.MIN_VALUE would fail the test node.val <= low. Bounds strictly outside the int range cannot collide with any real key. (Another common fix is to pass Integer objects with null meaning “unbounded”.)

Dry run on Example 3:

node allowed range inside?
5 (-∞, +∞) yes
4 (-∞, 5) yes
6 (5, +∞) yes
3 (5, 6) no, return false

Key 7 is never visited because && short-circuits once the left side fails.

Complexity. Time O(n): each node is checked once in constant time. Space O(h) for the recursion: O(log n) for a balanced tree, O(n) for a chain.

Edge cases and pitfalls