The idea

A tree is a graph with no cycles and one path between any two nodes. That absence of cycles is what makes tree algorithms simpler than graph algorithms: you never need a visited set, because you cannot arrive anywhere twice.

Nearly every tree problem is one sentence about a node plus its children. "The depth is one more than the deeper subtree." "The tree is balanced if both subtrees are balanced and their depths differ by at most one." Write that sentence and the code follows.

Traversal order is the other half:

Pre-order (node, left, right) — copying a tree, serialising it.
In-order (left, node, right) — yields a binary search tree in sorted order.
Post-order (left, right, node) — anything needing children resolved first, like computing sizes or freeing nodes.
Level-order — a queue, not recursion. Use it when distance from the root matters.

A binary search tree adds an invariant: everything left is smaller, everything right is larger. That turns lookup into binary search — but only while the tree stays balanced. A BST built from sorted input degenerates into a linked list and every operation becomes O(n).

Walkthrough

A tree stored in an array: node i has children at 2i+1 and 2i+2. Watch the traversal walk down each branch and back.

What it costs

time: O(n) for a full traversal, O(h) for a BST lookup
space: O(h) for the recursion stack

Height h is log n for a balanced tree and n for a degenerate one. The gap between those two is why self-balancing trees exist.

When to reach for it

The data is genuinely hierarchical: a filesystem, a DOM, an org chart, a parse tree.
You need sorted order together with fast insertion — a balanced BST gives both.
You need range queries, a predecessor, or a successor, which hashing cannot answer.
The problem has a recursive definition, which a tree makes structural rather than incidental.

Rather than the obvious alternative

A hash map

Faster for exact lookup and simpler. Give it up when you need order: nearest key, range, or an in-order walk.

A sorted array

Same O(log n) search and far better cache behaviour, but insertion is O(n). Prefer the array when the data is static, the tree when it changes.

A graph

A tree is a graph with no cycles, which is what lets you drop the visited set. If the structure can contain cycles, it is not a tree and the traversal needs one.

How to spot it

The data is hierarchical: filesystem, DOM, org chart, parse tree.
The problem mentions parent, child, leaf, root, or depth.
You need sorted order with fast insertion, which is a BST's in-order walk.
A recursive definition falls out naturally from the statement.

Where it goes wrong

Forgetting the empty tree

`null` is a valid tree and usually the base case. Most tree bugs are a missing null check at the top.

Assuming balance

A BST is only O(log n) while it stays balanced. Sorted insertions produce a linked list with extra pointers.

Confusing depth and height

Depth is measured from the root down, height from a node to its deepest leaf. Problems use both, and swapping them gives an off-by-one that only shows on lopsided trees.

Practise it

Build it

The problems above are one function each. These assemble the same ideas into a working thing across several files.