Trees & BST Traversal

A tree is a graph with no cycles and a single designated root. Every node has at most one parent. Trees show up everywhere — filesystems, DOM, syntax trees, routing tables, database indexes — and the binary search tree in particular turns the "walk a tree" skill into a useful data structure for searching and sorting.

What a tree is (and isn't)

• Tree. Connected graph with no cycles. Exactly one node has no parent — that's the root. Every other node has exactly one parent. Nodes with no children are leaves. The longest root-to-leaf path is the tree's height.
• Binary tree. A tree where every node has at most two children — conventionally named left and right. Binary-ness gives us a clean recursive shape: "tree = root + left subtree + right subtree".
• Binary search tree (BST). A binary tree with an extra invariant: for every node, all values in its left subtree are strictly less than the node, and all values in its right subtree are strictly greater. That ordering invariant is what makes the data structure useful — you can search, insert, and delete in O(log n) time when the tree is balanced.

A tree without the BST ordering is just a hierarchy — perfectly fine for layout and structure (a DOM isn't a BST), but you can't use it to answer "is this value in the set?" in sub-linear time.

The four traversals

Every time you "walk" a tree you're picking an order in which to visit its nodes. There are four you should recognise on sight.

Let's use this running example:

        50
       /  \
     25    75
    / \    / \
   10 30 60  80

In-order — left, node, right

Recurse left, emit the node, recurse right. On a BST this yields the sorted values: [10, 25, 30, 50, 60, 75, 80]. This is the most useful traversal in practice — it's how std::map iteration in C++ and TreeMap.entrySet() in Java yield keys in sorted order for free.

Pre-order — node, left, right

Emit this node first, then recurse. Output: [50, 25, 10, 30, 75, 60, 80]. The root shows up first, which is exactly the structure you want for serialising or cloning a tree — read it back and insert in pre-order and you reconstruct the same shape.

Post-order — left, right, node

Recurse into both children first, then emit this node. Output: [10, 30, 25, 60, 80, 75, 50]. Children before parents is the order you want for deletion or cleanup (free children before freeing their parent pointer), and for evaluating expression trees (operands before operators).

Level-order — BFS

The odd one out: instead of recursion, use a queue. Push the root, then in a loop pop-visit-enqueue-children. Output: [50, 25, 75, 10, 30, 60, 80] — the tree layer by layer, left-to-right at each depth. This is how you answer "what's the shortest path from root to X?" or "find all nodes at depth k" without doing extra work.

BST operations

Search. Start at the root. If the value equals the node, hit. Otherwise go left if the value is smaller, right if larger. Fall off a null pointer → miss. Each step halves the search space on a balanced tree, so search is O(log n) in the average case.

Insert. Same walk as search, but when you fall off, attach a new leaf in that slot. Always a leaf — no internal restructuring. Duplicates are usually handled by either rejecting them or using a count.

Delete — this one is tricky. Three cases:

1. Leaf. Remove the pointer from the parent. Done.
2. One child. Splice the child up in place of the deleted node.
3. Two children. Replace the deleted node with its in-order successor — the leftmost node in its right subtree. (Or symmetrically the in-order predecessor.) Then delete that successor from the right subtree, which is one of the first two easy cases.

Case 3 is the classic interview trap. Drawing it out on paper for delete(50) on the example tree is a good way to internalise the move.

When to use which

You want	Use
Sorted output from a BST	Inorder
Save/load a BST that reconstructs exactly	Preorder
Free children before parents	Postorder
Shortest path, BFS exploration, layer-by-layer	Level-order

"When does the root get visited?" is the quick way to tell the first three apart: first (pre), middle (in), last (post).

The degenerate BST trap

What happens if you insert values in sorted order — say [1, 2, 3, 4, 5]? Every value is larger than the last, so every insert goes right. The tree degenerates into a linked list.

  1
   \
    2
     \
      3
       \
        4
         \
          5

Search, insert, and delete on this shape are O(n), not O(log n). The BST you've built is no better than a linked list.

This is why real-world BSTs are self-balancing: they detect skew during inserts/deletes and rotate subtrees to keep the height at O(log n). The two famous schemes are AVL trees (strict balance — at each node, left and right subtrees differ in height by at most 1) and red-black trees (looser but cheaper to maintain). You don't usually implement these by hand — you reach for a standard-library map that's already a red-black tree under the hood.

Real-world BSTs

• C++ std::map / std::set — red-black tree under the hood. Iteration yields keys in sorted order because of inorder traversal.
• Java TreeMap / TreeSet — also red-black trees. Same inorder iteration guarantee.
• Database indexes — typically B-trees or B+-trees, not binary; they're a generalisation that's better suited to disk blocks, but the ordering-and-halving intuition is identical.
• Filesystem directories — not usually BSTs (ordering is by creation or name, not hash), but the traversal patterns apply directly when you walk a directory tree.
• Jump consistent hashing, skip lists, tries — relatives that trade slightly different invariants for slightly different performance characteristics, but all built on the same "tree = root + subtrees" recursion.

Playground

Use the Build values input to seed a tree — insert them in the order you list. Pick an operation (Insert, Search, or any traversal) and press Play to watch each step highlight the visited node and grow the visited list. Try inserting a sorted list and notice the degenerate right-leaning tree; then shuffle and insert again to see a more balanced shape.

Visualizer

The Tree Walker panel animates a seven-node BST with all four traversals. Flip through them back-to-back — inorder reads the sorted sequence left-to-right, level-order sweeps top-to-bottom — and the picture of "same tree, four different walks" sticks.