Binary Search Trees

A binary search tree is a binary tree with an ordering invariant: values in the left subtree are smaller, values in the right subtree are larger. That invariant enables search, sorted traversal, and range queries, but only if the tree shape stays reasonable.

The BST Invariant

The invariant applies to entire subtrees, not only direct children. Every node carries an allowed range. A right grandchild of the left child must still be less than the root.

Scenario: In-Memory Price Index

A marketplace keeps products ordered by price for quick range filters. A balanced search tree can support insert, lookup, and range traversal. But if inserts arrive sorted and the tree does not rebalance, it degenerates into a linked list.

Same Pattern in Java, Python, and JavaScript

BST search follows the invariant: target smaller goes left, target larger goes right.

class TreeNode { int value; TreeNode left; TreeNode right; }

class BstSearch {
    static boolean contains(TreeNode node, int target) {
        while (node != null) {
            if (target == node.value) return true;
            node = target < node.value ? node.left : node.right;
        }
        return false;
    }
}

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Return whether a binary tree is a valid BST.
• Return the kth smallest value in a BST.
• Return the sum of BST values between low and high inclusive.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

class Node { int val; Node left; Node right; }

class ValidateBst {
    static boolean isValid(Node root) {
        return valid(root, null, null);
    }

    static boolean valid(Node node, Integer low, Integer high) {
        if (node == null) return true;
        if (low != null && node.val <= low) return false;
        if (high != null && node.val >= high) return false;
        return valid(node.left, low, node.val) && valid(node.right, node.val, high);
    }
}

import java.util.*;
class Node { int val; Node left, right; }
class KthSmallest { static int kth(Node root, int k) { Deque<Node> stack = new ArrayDeque<>(); Node cur = root; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); cur = cur.left; } cur = stack.pop(); if (--k == 0) return cur.val; cur = cur.right; } throw new IllegalArgumentException(); } }

class Node { int val; Node left, right; }
class RangeSum { static int sum(Node node, int low, int high) { if (node == null) return 0; if (node.val < low) return sum(node.right, low, high); if (node.val > high) return sum(node.left, low, high); return node.val + sum(node.left, low, high) + sum(node.right, low, high); } }

Solved modelWorked Interview Answer

Validate whether a binary tree satisfies the full BST invariant. Carry inherited lower and upper bounds. Direct parent-child checks miss violations deeper inside a subtree.

class Node { int val; Node left; Node right; }

class ValidateBst {
    static boolean isValid(Node root) {
        return valid(root, null, null);
    }

    static boolean valid(Node node, Integer low, Integer high) {
        if (node == null) return true;
        if (low != null && node.val <= low) return false;
        if (high != null && node.val >= high) return false;
        return valid(node.left, low, node.val) && valid(node.right, node.val, high);
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Checking only direct children.
• Ignoring duplicates policy.
• Assuming BST is balanced.
• Not using inorder sorted property.
• Using BST where hash lookup is enough and order is irrelevant.

Execution guardrailQuick-Start Checklist

• Define duplicate policy.
• Carry min and max bounds.
• Use inorder for sorted traversal.
• State cost in terms of height.
• Mention balance assumptions.
• For range query, prune impossible subtrees.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice validate BST, kth smallest, LCA in BST, and range sum BST.
• Study AVL/red-black trees conceptually.
• Compare BSTs with hash maps and sorted arrays.