Trees: recursion made visual

01 · Foundation

A tree is a recursive definition

Here's the whole definition, and it's shorter than it looks: a tree is either empty (the base case — a null node, nothing there), or it's a node with a value, plus a left subtree and a right subtree — and each of those subtrees is, itself, just a smaller tree, following the exact same definition.

That self-reference is the whole point. It's why almost every solution on this page reduces to the same shape: handle the empty-node base case, then combine whatever the recursive calls on the left and right subtrees hand back. Counting nodes? count(node) = 1 + count(left) + count(right). Finding height? height(node) = 1 + max(height(left), height(right)). Same skeleton, different combining step.

02 · Traversals

The three DFS orders, and when each one matters

All three depth-first orders visit the exact same nodes — the only thing that changes is when the current node gets processed relative to its two children. That single ordering choice is what each name encodes:

• Inorder (left, node, right) — visit the whole left subtree, then the node, then the whole right subtree. On a Binary Search Tree specifically, this visits every value in ascending sorted order — no sorting step required. Reach for inorder whenever you need sorted output from a BST.
• Preorder (node, left, right) — visit the node itself before either child. This is the order to use when you need to copy or serialize a tree, since a preorder list lets you rebuild the exact same shape later, or any time a parent's value needs to be known before its children are processed.
• Postorder (left, right, node) — visit both children before the node itself. Use this whenever a node needs information from its children first — deleting a tree bottom-up (children must be freed before their parent), or evaluating an expression tree (you need both operand values before you can apply the operator).

Here's a small BST — root 5, left child 3, right child 8, with 3's own children 1 (left) and 4 (right):

03 · Breadth-first

Level-order (BFS) — when depth matters

All three orders above are depth-first: they dive all the way down one branch before backtracking to another. Level-order is a different shape entirely — it visits the tree row by row, top to bottom, and left to right within each row. On the tree above that means 5, then 3, 8, then 1, 4.

The mechanism is different too: level-order is driven by a queue, not recursion. You push the root, then repeatedly pop a node, visit it, and push its children — which naturally processes everything one level before moving to the next. Reach for it whenever you specifically need "distance from the root" or a level-by-level view, since none of the three DFS orders give you that naturally — they all commit to one branch before even seeing the sibling branches at the same depth.

04 · The BST rule

BST — a search invariant, not just a shape

A Binary Search Tree isn't defined by how it looks — it's defined by one rule that holds at every single node: everything in that node's left subtree is smaller than it, and everything in its right subtree is larger.

That invariant is the entire reason BSTs are fast. At any node during a search, insert, or delete, you don't need to check both subtrees — the invariant already tells you which side the value you're looking for has to be on. Compare, then go left or go right. It's the exact same halving idea as binary search over a sorted array, just walking down a tree's branches instead of shrinking an array's index range.

05 · Method

A repeatable framework for tree problems

1. 1 Recognize the recursive structureCan you describe the answer for a tree purely in terms of the same answer applied to its left and right subtrees? If yes, the problem is recursion-shaped.
2. 2 Pick the traversal order by timingDecide when you need to process the current node relative to its children: before both = preorder, between them = inorder, after both = postorder. Need row-by-row output instead? Reach for level-order (BFS) rather than any DFS order.
3. 3 Define the base case explicitlyAn empty/null node, always, before you write a single line of the recursive case. Skipping this is the single most common source of tree bugs.
4. 4 Use the BST invariant to pick a directionFor search, insert, and delete on a BST, compare against the current node and go left or right — never check both subtrees "just in case."
5. 5 Question the tree's shapeA BST built by inserting already-sorted input degenerates into a straight chain — no better than a linked list. Don't assume height is log n just because it's a BST.

06 · Worked example

Inserting into a BST, one value at a time

Starting from an empty BST, insert 5, 3, 8, 1, 4 in that order. Every insert walks down from the root using the same left-smaller / right-larger rule, and places the new value the moment it finds an empty spot.

Tracing it out: 5 arrives first and becomes the root, since the tree is empty. 3 is smaller than 5, so it goes left — the left spot is empty, so it settles there. 8 is larger than 5, so it goes right and settles there. 1 is smaller than 5 (go left, to 3), then smaller than 3 (go left again) — the spot is empty, so 1 becomes 3's left child. 4 is smaller than 5 (go left, to 3), then larger than 3 (go right) — that spot is empty too, so 4 becomes 3's right child.

That's exactly the tree drawn in the diagram above — which is why its inorder traversal came out sorted: 1, 3, 4, 5, 8.

07 · Complexity

How to reason about time & space

• BST search / insert / delete — O(h), where h is the tree's height. That's O(log n) if the tree stays reasonably balanced, but degrades to O(n) worst case if it collapses into a chain. Self-balancing trees like AVL or Red-Black trees exist specifically to guarantee O(log n) height — out of scope here, but worth knowing they exist.
• Any full traversal (preorder, inorder, postorder, or level-order) — O(n), since every node is visited exactly once, no matter the order.
• Auxiliary space — the three DFS orders use O(h) space for the recursive call stack. Level-order (BFS) instead uses O(w) space for its queue, where w is the tree's maximum width (the most nodes in any single row).

08 · Before you start coding

Common mistakes

• Mixing up the three DFS orders — a very common interview slip, since "left, node, right" vs "node, left, right" vs "left, right, node" look deceptively similar until you're mid-explanation.
• Forgetting the null/empty-node base case, which causes a crash instead of a clean recursive bottom-out.
• Assuming a BST is balanced when it might be a degenerate chain — especially dangerous when the input happens to already be sorted.
• Using recursion for BFS/level-order — it needs an explicit queue, since it processes breadth-first (row by row), not depth-first the way the call stack naturally would.
• When validating whether a tree is a valid BST, comparing a node only against its immediate parent instead of its full ancestor path — validity depends on a range inherited from every ancestor above, not just the one directly above it.

09 · Try it yourself

See each traversal animate

Each card below links to the matching interactive visualizer, where you can step through the traversal or operation node by node.