Binary Search Tree (BST)

The intuition: a dictionary you open in the middle

How do you look up a word in a paper dictionary? You open it roughly in the middle. If the word you want comes later in the alphabet, you flip right; if earlier, left. With every step, half the book drops out.

A binary search tree (BST) works on the same principle. You could say it's binary search "frozen" into the shape of a tree.

The BST property

For every node, two conditions hold:

• all values in the left subtree are less than the node's value;
• all values in the right subtree are greater than the node's value.

The word "all" is the key here. It's not enough for the left child to be smaller than its parent: the node's entire left subtree has to be smaller.

Usually a BST is assumed to have no duplicates. If they're possible, agree with the interviewer on where they go: left or right.

Search: following a single trail

Let's search for 6 in the tree above:

1. The root holds 8. Six is smaller, so we go left.
2. Here we have 3. Six is larger, so we go right.
3. Here we have 6. Found it!

At each step we go down one level and discard an entire subtree. That's why search costs O(h), where h is the height of the tree.

Insertion: find the spot where it "should have been"

Insertion is barely different from search. You go left or right the same way until you hit an empty spot (null). That's where you attach the new node. The new element always becomes a leaf, and the rest of the tree doesn't need to be rearranged.

For example, inserting 7 follows the path 8 → 3 → 6. The right child of 6 is empty, so that's where 7 goes.

class Node:
    def __init__(self, val):
        self.val, self.left, self.right = val, None, None

def search(root, x):
    # go down until we find it or hit an empty spot
    while root and root.val != x:
        root = root.left if x < root.val else root.right
    return root

def insert(root, x):
    if root is None:
        return Node(x)          # found an empty spot, attach a leaf
    if x < root.val:
        root.left = insert(root.left, x)
    elif x > root.val:
        root.right = insert(root.right, x)
    return root                 # duplicates are ignored

In-order traversal gives you sorted order

Remember in-order: left subtree → node → right subtree. In a BST, everything on the left is smaller than the node and everything on the right is larger. So this traversal yields the values in ascending order: 1, 3, 6, 8, 9, 10, 14.

This is a very handy fact, so keep it in mind:

• need the k-th smallest element? Do an in-order traversal and count steps;
• need the contents sorted? Do an in-order traversal, no sorting required.

How to check that a tree is a BST

Here's a classic trap. Look at this tree:

The check "left child smaller, right child larger" passes here, yet the tree is still invalid. Comparing only with the parent isn't enough.

The right idea is bounds. Every node has an allowed range (min, max):

• the root's range is (−∞, +∞);
• going left, you tighten the upper bound to the current node's value;
• going right, you tighten the lower bound.

In the example, node 6 gets the range (3, 5), and 6 isn't in it. So the tree is not a BST.

There's an alternative too: do an in-order traversal and check that the sequence is strictly increasing. Both approaches run in O(n). You'll solve this problem yourself in the chapter's practice.

Balance: why h can be n

Everywhere we wrote O(h), not O(log n). Here's why. Try inserting the numbers 3, 2, 1 in that order:

What you get is essentially a linked list. The height is h = n, and search becomes O(n).

Tree shape	Height h	Search / insert
Balanced	≈ log n	O(log n)
Degenerate ("stick")	n	O(n)

To keep the height logarithmic at all times, there are self-balancing trees: AVL and red-black trees. They power TreeMap in Java and std::map in C++. You're almost never asked to implement them in an interview, but it's useful to know they exist.

How it sounds in an interview

"This is a BST, so search runs in O(h): at each step I discard one subtree. In a balanced tree that's O(log n); in the worst case, if the tree has degenerated, it's O(n). An in-order traversal gives sorted order, and that's what I'll use."

Common mistakes

• Comparing a node only with its children when validating a BST. You need bounds passed down through the whole depth.
• Saying "BST search is O(log n)" without a caveat. The correct version: O(h), and log n only for a balanced tree.
• Using int as ±∞ for the bounds. If the tree contains Integer.MIN_VALUE, the check breaks. Use null or long.
• Forgetting return root in recursive insertion. Then the new node gets lost and never attaches to the tree.

You now know the BST property, search, and insertion, and every problem in this chapter builds on exactly these.