Introduction to BST

Easy TUF ID 1153 A2Z

What this covers

A binary search tree (BST) is a binary tree with one extra rule about where keys may live. That single rule turns the tree into a sorted structure: searching, inserting, deleting, finding the minimum, the floor of a value or the k-th smallest key all become a walk downwards from the root that never backtracks. This article states the rule precisely, shows the most common way to get it wrong, explains why an inorder traversal of a BST comes out sorted, and shows why the cost of every operation is the tree’s height, which in turn depends on the order in which the keys arrived.

All code here uses this node type, the same one used in the other BST articles:

static class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
}

The empty tree is represented by a null root, exactly as an empty linked list is a null head.

The BST property

A binary tree is a BST when, for every node x:

every key in the left subtree of x is smaller than x.val, and
every key in the right subtree of x is larger than x.val.

The rule is about whole subtrees, not just children. Here is the standard example:

          8
        /   \
       3     10
      / \      \
     1   6      14
        / \     /
       4   7   13

Check node 3: its left subtree is {1}, all smaller; its right subtree is {6, 4, 7}, all larger. Check the root 8: the left subtree {3, 1, 6, 4, 7} lies entirely below 8 and the right subtree {10, 14, 13} entirely above. Every node passes, so this is a BST.

An equivalent way to see it is that every node owns a window (low, high) of keys it is allowed to hold. The root’s window is unbounded. Stepping left from a node with key v keeps the lower bound and shrinks the upper bound to v; stepping right raises the lower bound to v. Node 6 above lives in the window (3, 8): it is right of 3 and left of 8. Node 4 lives in (3, 6), and node 13 in (10, 14).

The common mistake: checking only the children

It is tempting to verify the property by comparing each node with its two children:

static boolean isBSTLocalOnly(TreeNode node) {
    if (node == null) return true;
    if (node.left != null && node.left.val >= node.val) return false;
    if (node.right != null && node.right.val <= node.val) return false;
    return isBSTLocalOnly(node.left) && isBSTLocalOnly(node.right);
}

This accepts trees that are not BSTs:

        5
       / \
      3   8
     / \
    1   6        <- 6 > 5, yet it sits in the left subtree of 5

Every parent-child pair is fine (3 < 5, 8 > 5, 1 < 3, 6 > 3), but 6 is in the left subtree of 5 and is larger than 5. A search for 6 starting at the root would turn right at 5 and never find it, so the tree is broken for the very operation BSTs exist for. The correct check carries the window down the tree:

static boolean isBST(TreeNode root) {
    return isBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

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

The bounds are long so that keys equal to Integer.MIN_VALUE or Integer.MAX_VALUE are still strictly inside the starting window. Starting with int bounds set to those extremes would reject a valid tree that contains one of them; the Java file tests exactly that case.

Inorder traversal is sorted

An inorder traversal visits the left subtree, then the node, then the right subtree:

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

For a BST this produces the keys in increasing order. The argument is a short induction on the size of the tree. The left subtree is a smaller BST, so it is printed in increasing order, and all of its keys are below the node. Then comes the node itself. Then the right subtree, again sorted, with every key above the node. Three sorted runs, each entirely below the next, join into one sorted run. On the example tree the output is 1 3 4 6 7 8 10 13 14.

The converse also holds: a binary tree whose inorder sequence is strictly increasing is a BST. That gives a second way to validate a tree, and on the broken tree above the inorder sequence 1 3 6 5 8 exposes the violation at once.

This one fact powers a large share of BST problems. The k-th smallest key is the k-th node visited in inorder. Two sum on a BST is two pointers over the inorder sequence. Repairing a BST in which two nodes were swapped means finding the places where the inorder sequence goes down.

Why BSTs are useful: every operation costs O(h)

At any node, a single comparison with node.val tells you which one subtree can contain the target. The other subtree is discarded without being looked at, so a search follows one root-to-leaf path:

static boolean contains(TreeNode root, int key) {
    TreeNode cur = root;
    while (cur != null && cur.val != key) {
        cur = key < cur.val ? cur.left : cur.right;   // the key can only be on one side
    }
    return cur != null;
}

The number of nodes visited is at most the height h, the number of nodes on the longest root-to-leaf path:

static int height(TreeNode node) {
    if (node == null) return 0;
    return 1 + Math.max(height(node.left), height(node.right));
}

Insertion is the same walk. Go left or right until you fall off the tree; the empty spot where you fell off is where the new key belongs, because the key agrees with every comparison made on the way down.

static TreeNode insert(TreeNode root, int key) {
    if (root == null) return new TreeNode(key);       // fell off the tree: this is the key's spot
    if (key < root.val) root.left = insert(root.left, key);
    else if (key > root.val) root.right = insert(root.right, key);
    return root;                                      // key == root.val: already present, nothing to do
}

Deletion, minimum and maximum, floor and ceil, successor and predecessor all follow the same pattern and all cost O(h) time.

The shape depends on the insertion order

O(h) is only good news when h is small. A BST with n nodes has a height somewhere between about log2 n and n, and which one you get depends on the order of insertions:

static TreeNode buildByInsertion(int[] keys) {
    TreeNode root = null;
    for (int k : keys) root = insert(root, k);
    return root;
}

Inserting 2, 1, 3 gives root 2 with two children: height 2. Inserting 1, 2, 3 gives 1, whose right child is 2, whose right child is 3: a chain of height 3. Both trees hold the same keys and produce the same inorder sequence; only the shape differs. In general, inserting keys in sorted order produces a chain in which every node has only a right child, and the BST degenerates into a linked list. The Java file inserts 1..1000 in order and gets height 1000, so a search for 1000 touches every node.

When all keys are known up front you can avoid this by building from the sorted array: make the middle element the root, then build the left half and the right half the same way.

static TreeNode buildBalanced(int[] sorted, int lo, int hi) {
    if (lo > hi) return null;
    int mid = (lo + hi) >>> 1;
    TreeNode node = new TreeNode(sorted[mid]);
    node.left = buildBalanced(sorted, lo, mid - 1);
    node.right = buildBalanced(sorted, mid + 1, hi);
    return node;
}

Every level halves the range, so the height is floor(log2 n) + 1, which is 10 for 1000 keys. A search now needs at most 10 comparisons instead of 1000. When keys arrive one at a time and you still need a guaranteed logarithmic height, you need a self-balancing BST such as an AVL tree or a red-black tree, which rotate nodes after updates to keep the height in check. Java’s TreeMap and TreeSet are red-black trees, which is why all their operations are O(log n).

Operation	Balanced BST	Skewed BST (chain)	Sorted array
Search	`O(log n)`	`O(n)`	`O(log n)`
Insert or delete	`O(log n)`	`O(n)`	`O(n)` because of shifting
Minimum or maximum	`O(log n)`	`O(n)`	`O(1)`
All keys in order	`O(n)`	`O(n)`	`O(n)`

Duplicates

The definition above uses strict inequalities, so each key appears at most once. That is the convention in nearly every interview problem. When duplicates matter there are three standard choices: ignore repeated inserts (what insert above does), keep a count in each node, or relax one side of the rule, for example “equal keys always go right”. Whichever you pick, every operation must use the same convention, or searches will look on the wrong side.

Edge cases and pitfalls

Empty tree. A null root is a valid BST with height 0. Every operation must handle it before touching root.val.
Checking only children. Not sufficient. Carry a (low, high) window down the tree, or check that the inorder sequence is increasing.
int sentinels. Bounds initialised to Integer.MIN_VALUE and Integer.MAX_VALUE wrongly reject trees containing those keys. Use long bounds or null for “no bound”.
Logarithmic is not automatic. A plain BST is fast only when balanced. Sorted or nearly sorted input produces a chain.
Recursion depth. On a chain, recursive operations go n calls deep. For very deep trees prefer iterative versions, which need O(1) extra space.
Same keys, different trees. Two BSTs can hold identical keys in different shapes. Compare inorder sequences when you mean “same keys”, and compare structure when you mean “same tree”.

Search in a Binary Search Tree is the contains walk returning the node itself.
Find Min/Max in BST walks the left and right edges of the tree.
Insert a given node in BST develops insert in recursive and iterative form.
Delete a node in BST is the one basic operation that has to restructure the tree.
Check if a tree is a BST or not turns the window check into a full problem.
Kth Smallest and Largest element in BST uses the sorted inorder order directly.
Inorder Traversal of Binary Tree covers the traversal itself in detail.