Trees & Binary Search Trees

A tree is a set of nodes where each node has one parent (except the root) and no cycles. That single constraint is what makes trees useful: it guarantees exactly one path between any two nodes, so "where is X" and "how do I get to X" have unique answers.

A binary search tree adds an ordering invariant on top, and that invariant is what turns a tree into a searchable structure.

Core Concepts

Term	Meaning
Root	The single node with no parent
Leaf	A node with no children
Height	Longest root-to-leaf path, in edges. Determines every operation's cost
Depth	Distance from the root to a given node
Binary tree	Each node has at most two children
Complete	Every level full except possibly the last, filled left to right
Balanced	Height stays $O(\log n)$ as nodes are added — see Balanced Trees

Mechanism

The BST invariant

For every node: everything in the left subtree is smaller, everything in the right subtree is larger.

Every value left of 8 is below it, every value right of it is above — and the same holds recursively at 3, at 6, and at every other node. Wikimedia Commons, Public domain

That invariant makes search a sequence of one-way decisions. Looking for 7: at 8 go left, at 3 go right, at 6 go right, found — three comparisons instead of nine.

Python

def search(node, key):
    while node:
        if key == node.value:
            return node
        node = node.left if key < node.value else node.right
    return None

def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.value:
        node.left = insert(node.left, key)
    elif key > node.value:
        node.right = insert(node.right, key)
    return node          # equal keys ignored; a real implementation decides a policy

C++

#include <vector>

struct Node {
    int value;
    Node* left = nullptr;
    Node* right = nullptr;
};

Node* search(Node* node, int key) {
    while (node) {
        if (key == node->value) return node;
        node = key < node->value ? node->left : node->right;
    }
    return nullptr;
}

Node* insert(Node* node, int key) {
    if (!node) return new Node{key};
    if (key < node->value)      node->left  = insert(node->left, key);
    else if (key > node->value) node->right = insert(node->right, key);
    return node;        // equal keys ignored; a real implementation decides a policy
}

Both are $O(\text{height})$. The entire question is therefore what the height is.

Building a BST, traced

Inserting 5, 1, 8, 3 in that order, one node at a time:

insert 5     5 becomes the root (empty tree)

insert 1     5
            /
           1                  1 < 5, go left, insert as 5's left child

insert 8     5
            / \
           1   8              8 > 5, go right, insert as 5's right child

insert 3     5
            / \
           1   8
            \
             3                3 > 1 (go right), 3 < 5 already decided — insert as 1's right child

An in-order walk (left, node, right) of the final tree visits 1, 3, 5, 8 — sorted, exactly as the invariant guarantees:

Python

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

root = None
for key in (5, 1, 8, 3):
    root = insert(root, key)

assert root.value == 5 and root.left.value == 1 and root.right.value == 8
assert root.left.right.value == 3      # 3 landed as 1's right child, not 5's

def in_order(node):
    if node:
        yield from in_order(node.left)
        yield node.value
        yield from in_order(node.right)

assert list(in_order(root)) == [1, 3, 5, 8]

C++

#include <cassert>

Node* build_traced_tree() {
    Node* root = nullptr;
    for (int key : {5, 1, 8, 3}) root = insert(root, key);

    assert(root->value == 5 && root->left->value == 1 && root->right->value == 8);
    assert(root->left->right->value == 3);   // 3 landed as 1's right child, not 5's
    return root;
}

Deletion, and the one case that is awkward

Removing a node with zero or one child is a splice. Removing a node with two children cannot be — neither child can take its place without violating the invariant. The fix is to replace the value with its in-order successor (the smallest value in the right subtree), then delete that successor, which by construction has at most one child:

Python

def delete(node, key):
    if node is None:
        return None
    if key < node.value:
        node.left = delete(node.left, key)
    elif key > node.value:
        node.right = delete(node.right, key)
    else:
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        succ = node.right                    # smallest value greater than node
        while succ.left:
            succ = succ.left
        node.value = succ.value
        node.right = delete(node.right, succ.value)
    return node

C++

Node* remove(Node* node, int key) {          // named remove — delete is a keyword
    if (!node) return nullptr;
    if (key < node->value) {
        node->left = remove(node->left, key);
    } else if (key > node->value) {
        node->right = remove(node->right, key);
    } else {
        if (!node->left)  { Node* r = node->right; delete node; return r; }
        if (!node->right) { Node* l = node->left;  delete node; return l; }
        Node* succ = node->right;                // smallest value greater than node
        while (succ->left) succ = succ->left;
        node->value = succ->value;
        node->right = remove(node->right, succ->value);
    }
    return node;
}

Traversals

Order	Visits	Produces	Used for
In-order	left, node, right	Sorted sequence — for a BST	Iterating in key order
Pre-order	node, left, right	Root first	Copying/serialising a tree
Post-order	left, right, node	Children before parents	Freeing memory, evaluating expressions
Level-order	Breadth-first by depth	Row by row	Printing, shortest path in an unweighted tree

Python

def in_order(node):
    if node:
        yield from in_order(node.left)
        yield node.value                  # sorted output for a BST
        yield from in_order(node.right)

assert list(in_order(root)) == [1, 3, 5, 8]     # confirms the traced tree from above

C++

void in_order(Node* node, std::vector<int>& out) {
    if (!node) return;
    in_order(node->left, out);
    out.push_back(node->value);          // sorted output for a BST
    in_order(node->right, out);
}

void confirm_in_order() {
    std::vector<int> out;
    in_order(build_traced_tree(), out);
    assert((out == std::vector<int>{1, 3, 5, 8}));    // confirms the traced tree from above
}

In-order traversal of a BST yielding sorted output is not a coincidence — it is the invariant restated. It also gives a neat correctness check: if an in-order walk is not sorted, the tree is not a valid BST.

Edge Cases & Pitfalls

An unbalanced BST is a linked list wearing a costume

Insert 1, 2, 3, 4, 5 into a plain BST in that order and every node becomes the right child of the previous one. Height is n, and every operation is $O(n)$ — with worse constants than an actual linked list, because each node also carries an unused pointer.

Sorted or nearly-sorted insertion order is not an unusual case; it is one of the most common ways real data arrives. This is the entire reason balanced trees exist, and why you should almost never use a hand-rolled plain BST in production code.

• Recursive traversal is $O(height)$ in stack space. On a degenerate tree that is $O(n)$ frames and a possible stack overflow. Use an explicit stack for untrusted input.
• Duplicate keys need an explicit policy — reject, count, or keep a list per node. Silently dropping them (as the insert above does) is a decision, so make it deliberately.
• validate_bst by checking each node against its children is wrong. The invariant is about entire subtrees, not immediate children; the correct check passes a (min, max) range down.

Comparisons

	BST (unbalanced)	Balanced BST	Hash table
Search / insert / delete	$O(\log n)$ avg, $O(n)$ worst	$O(\log n)$ guaranteed	$O(1)$ expected
Sorted iteration	Yes	Yes	No
Range queries, min/max	Yes	Yes	No
Worst case	Degenerate	Bounded	$O(n)$

Recall

InvariantAt every node, everything in the left subtree is smaller and everything in the right subtree is larger.

Costs

search / insert / delete (average)$O(\log n)$

search / insert / delete (worst, degenerate)$O(n)$

in-order traversal, all n nodes (worst)$O(n)$

find min/max (worst)$O(height)$

Reach for itYou need sorted iteration, range queries, or predecessor/successor, and can tolerate $O(n)$ worst case without extra bookkeeping.

TrapInserting already-sorted or nearly-sorted data into a plain BST — it degenerates into a linked list with $O(n)$ height, silently losing every asymptotic advantage the structure was chosen for.

References

• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Ch. 12 — binary search trees, including the expected-height analysis for random insertion order.
• Sedgewick & Wayne, Algorithms, 4th ed., §3.2 — BSTs with a full implementation and empirical measurements.

Books & Videos

• VisuAlgo — Binary Search Tree — step through insertion, deletion and the successor case interactively.

Related Pages

• Balanced Trees — how AVL, red-black and B-trees keep the height logarithmic.
• Heaps & Priority Queues — a different tree invariant, for a different question.
• Indexing & Storage Engines — B-trees in the setting that motivated them.