Binary Search Trees

On this page

The Idea
Build It
Know It
Break It
Use It

Quick reference

search(root, target)	O(h)
insert(root, value)	O(h)
delete(root, value)	O(h)
findMin / findMax	O(h)
Inorder traversal	O(n)

The Idea

A binary search tree is a binary tree with exactly one extra rule bolted on: for every node, everything in its left subtree is smaller than it, and everything in its right subtree is bigger. Same Node shape as last topic, same left/right pointers — the only thing that changed is a promise about what those pointers mean.

That one rule turns the tree into a guessing game. Picture the number-guessing game where you pick a secret number and every guess gets answered 'higher' or 'lower' — never the exact distance, just a direction. Each answer throws away half of whatever range was still possible. A BST plays that exact game with real data: standing at any node, comparing your target to node.value tells you which entire subtree to search next, and lets you ignore the other one completely, without looking at a single value inside it.

That's the halving idea, and it's new here — nothing earlier in this course relied on it. A plain binary tree from the last topic has no such rule, so finding a value means checking nodes with no way to rule anything out in advance; you might have to look at all of them. A BST's ordering promise is what makes 'ignore half the tree' a safe move instead of a guess.

One ordering rule — left is smaller, right is bigger — is the entire difference between a binary tree and a binary search tree. Every operation below is just 'compare, then go left or go right,' repeated until you land where you need to be.

Build It

The node — same shape, new promise

structure Node:
    value
    left          // -> Node, and every value in this subtree is < node.value
    right         // -> Node, and every value in this subtree is > node.value

// the ordering rule holds at every node, not just between direct parent and child

search — compare, then go left or right

function search(node, target):
    if node is NULL:                       // base case — ran out of tree, not found
        return NULL
    if target == node.value:
        return node
    if target < node.value:
        return search(node.left, target)   // rule out the entire right subtree
    return search(node.right, target)      // rule out the entire left subtree

This is the halving idea from The Idea, written down: one comparison, one subtree discarded whole, every step. If the tree is balanced, that's log₂(n) comparisons to check n values — the same halving pattern Recursion Basics' fast pow(x, n) used to cut n in half every call.

insert — navigate to the first empty spot, and place it there

function insert(node, value):
    if node is NULL:                        // found an empty spot — this is where value belongs
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    else if value > node.value:
        node.right = insert(node.right, value)
    return node                             // unchanged if value is already in the tree

Same navigation as search — compare, go left or right — except it keeps going past where search would give up (a NULL), and drops the new node there instead of reporting failure.

delete — three cases, by how many children the target has

function delete(node, value):
    if node is NULL:
        return NULL                          // value isn't in the tree — nothing to do
    if value < node.value:
        node.left = delete(node.left, value)
    else if value > node.value:
        node.right = delete(node.right, value)
    else:
        // this is the node to remove
        if node.left is NULL:
            return node.right                // leaf (both NULL) or one right child — splice it up
        if node.right is NULL:
            return node.left                 // one left child — splice it up
        // two children: steal the in-order successor's value, then delete the successor
        successor = findMin(node.right)      // smallest value in the right subtree
        node.value = successor.value
        node.right = delete(node.right, successor.value)
    return node

The two-children case is the only tricky one. You can't just remove the node — something has to take its place while keeping the ordering rule true for every value still in the tree. The in-order successor (the smallest value bigger than node.value) is exactly that replacement: copy its value up, then delete it from where it actually was — and it's guaranteed to have at most one child, so that inner delete always lands in the easy cases above.

findMin / findMax — leftmost and rightmost node

function findMin(node):
    while node.left is not NULL:
        node = node.left
    return node

function findMax(node):
    while node.right is not NULL:
        node = node.right
    return node

validate — check the ordering rule with an inherited (min, max) range

function validate(node, min = -Infinity, max = +Infinity):
    if node is NULL:
        return true                          // an empty subtree can't violate anything
    if node.value <= min or node.value >= max:
        return false
    return validate(node.left, min, node.value) and validate(node.right, node.value, max)

A node only being bigger than its immediate left child and smaller than its immediate right child is not enough — the rule has to hold against every ancestor, not just the one directly above. Passing (min, max) down the recursion carries the full inherited range: going left tightens the upper bound to the parent's value, going right tightens the lower bound, and those bounds accumulate from every ancestor above, not just the last one.

Know It

search, insert, and delete all walk one path from root to some node, so all three cost O(h) time and O(h) recursion-stack space, where h is the tree's height — O(log n) if the tree is balanced, O(n) worst case if it's skewed (direct callback to Binary Trees' skewed-tree edge case). findMin/findMax walk the same kind of single path but iteratively, so O(h) time and O(1) space — no stack needed. Inorder traversal, inherited unchanged from Binary Trees, gets a new property here: on a BST it visits every value in sorted order, for free, still O(n).

Operation	Time	Space	Why
search(root, target)	O(h)	O(h)	One comparison per level, one subtree discarded each time — O(log n) if balanced, O(n) if the tree has degenerated into a chain.
insert(root, value)	O(h)	O(h)	Same navigation as search, continued one step further to the first empty spot.
delete(root, value)	O(h)	O(h)	Locating the node is O(h); the two-children case adds one more O(h) walk to findMin and one more O(h) delete of the successor — still O(h) total, not O(h²), since the successor search happens inside the right subtree's own height.
findMin / findMax	O(h)	O(1)	A plain iterative walk down one side of the tree — no recursion, so no stack frames pile up.
Inorder traversal	O(n)	O(h)	Same traversal as Binary Trees, every node visited once — but the BST's ordering rule means left-root-right now visits every value from smallest to largest, with no sorting step required.

Break It

Inserting already-sorted data degenerates into a linked list

values arrive in sorted (or reverse-sorted) order, one insert at a time

Inserting 1, 2, 3, 4, 5 in that order: 1 becomes the root, 2 is bigger so it becomes 1's right child, 3 is bigger than both so it goes further right, and so on — every node ends up with only a right child, the exact skewed shape Binary Trees warned about. search/insert/delete all degrade from the expected O(log n) to O(n), because h has grown to equal n. The BST gives you no protection against this on its own — keeping the tree balanced under sorted insertions needs extra machinery this topic doesn't cover.

Deleting a two-children node without finding the true successor

the delete implementation grabs the wrong replacement value

The replacement for a deleted two-children node has to be the smallest value in its right subtree specifically — not just "some" nearby value, and not the right child itself unless the right child happens to have no left child of its own. Grab the wrong node (say, the right child directly, skipping past its left subtree) and the ordering rule breaks silently: a later search for a value that's still technically in the tree can walk the wrong direction and report it missing.

Validating against only the immediate parent or children

the check compares a node to node.left.value and node.right.value directly, with no inherited range

A node can be bigger than its immediate left child and smaller than its immediate right child and still break the tree's ordering rule against an ancestor further up. Concretely: a right child's left grandchild must still be smaller than the original root, not just smaller than its own parent — a purely local, parent-to-child comparison misses violations like that entirely. The (min, max) bound from Build It's validate() is what catches it, because the bound accumulates from every ancestor, not just the nearest one.

Duplicate values with no consistent left-or-right rule

the same value is inserted more than once

search/insert/delete all rely on strict less-than and greater-than to decide which single direction to go. If duplicates are allowed, insert has to pick one consistent side for equal values — always left, or always right — and every other operation must agree with that same choice. Pick inconsistently (some code paths send equal values left, others right) and search can walk past a value that's actually sitting in the tree, because it looked on the side nothing agreed to put it on.

Use It

Search in a Binary Search Tree

search() from Build It, verbatim.

Easy

Insert into a Binary Search Tree

insert() from Build It, verbatim.

Medium

Delete Node in a BST

delete() from Build It — the three cases (leaf/one child/two children) are the entire problem.

Medium

Validate Binary Search Tree

validate() from Build It — the (min, max) bound, not a local parent/child comparison. See Break It if the naive version passes your own tests but fails LeetCode's.

Medium

Lowest Common Ancestor of a Binary Search Tree

Use the ordering rule to skip searching entirely: if both target values are less than node.value go left, if both are greater go right, and the first node where they split (one on each side, or one equal to node.value) is the answer.

Medium

Kth Smallest Element in a BST

Inorder traversal visits values in sorted order for free — run inorder() from Build It and stop at the k-th value appended.

Medium

Convert Sorted Array to Binary Search Tree

Pick the middle element as the root, recurse on the left half for node.left and the right half for node.right — the halving idea from The Idea, run in reverse to build a balanced tree instead of search one.

Easy

Minimum Absolute Difference in BST

The smallest gap between any two values in a BST is always between two values that are adjacent in sorted order — run inorder() and check each value against the one right before it.

Easy

Range Sum of BST

Use the ordering rule to prune: if node.value is below the range, skip the entire left subtree; if it's above, skip the entire right subtree — don't visit nodes the rule already rules out.

Easy

Two Sum IV - Input is a BST

Run inorder() from Build It to get a sorted array for free, then reuse the Two Pointers pattern from Phase 1 on the result.

Easy