Trees and Traversals

Cost

Operation	Time	Space	Why
Any traversal (DFS or BFS)	O(n)	O(h)	Every node is entered once. DFS space is the height h; BFS space is the widest level, which is n/2 for a full tree.
BST search / insert / delete	O(h)	—	O(log n) when balanced, O(n) when the tree degenerates into a list. Unbalanced insertion of sorted data is exactly how that happens.
Balanced BST (AVL, red-black)	O(log n)	O(n)	Rotations keep h at O(log n) so the worst case matches the average. This is what a std::map or TreeMap gives you.
Height / diameter / subtree sums	O(n)	O(h)	Computed bottom-up: each node returns a summary to its parent, so one postorder pass answers what looks like a per-node question.

Reach for it when

Hierarchical data — file systems, org charts, the DOM, expression trees, decision trees.
Sorted data with frequent insertions, where an array would have to shift: a balanced BST keeps order at O(log n).
Range queries and "nearest value" lookups, which a hash map cannot answer at all.
Anything phrased per level, or asking for the shortest path in an unweighted structure — that is BFS.
Problems where a subtree's answer composes into its parent's, which is the signature of a bottom-up recursion.

The structure decides the code

A tree is defined recursively, so the code is too: handle the empty case, do something with the node, recurse into the children. Almost every question is that skeleton with the work moved around.

python

def walk(node):
    if not node:              # 1. base case, always first
        return
    # preorder work here
    walk(node.left)
    # inorder work here
    walk(node.right)
    # postorder work here

Where the work goes is the entire decision:

Work happens	Order	Good for
Before the calls	Preorder	Serialising, copying, passing context down
Between the calls	Inorder	BST → sorted sequence
After the calls	Postorder	Heights, diameters, subtree sums, deletion
In a queue loop	Level order	Per-level answers, shortest path

Top-down and bottom-up

Two ways to carry information, and picking the wrong one is what makes a tree problem feel hard.

Top-down: pass context into the recursion. Depth, accumulated path, permitted value range.

python

def is_bst(node, low=float("-inf"), high=float("inf")):
    if not node:
        return True
    if not low < node.value < high:
        return False
    return (is_bst(node.left, low, node.value)
            and is_bst(node.right, node.value, high))

Bottom-up: return a summary from the recursion and combine it at the parent.

python

def diameter(root):
    best = 0
    def height(node):
        nonlocal best
        if not node:
            return -1
        left, right = height(node.left), height(node.right)
        best = max(best, left + right + 2)   # path through this node
        return 1 + max(left, right)
    height(root)
    return best

The tell for bottom-up: the question is about a node's subtrees, and the answer is a maximum or a sum over all nodes. One pass, O(n) — computing height separately per node would be O(n²).

Breadth-first

Swap the stack for a queue and you walk level by level. Tracking the level boundary is the part worth memorising:

python

def levels(root):
    if not root:
        return []
    out, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):        # snapshot this level's size
            node = queue.popleft()
            level.append(node.value)
            queue.extend(c for c in (node.left, node.right) if c)
        out.append(level)
    return out

That len(queue) snapshot is what separates the levels; without it every node blends into one list. BFS is also the only correct choice for "fewest steps" questions — depth-first finds a path, not the shortest.

Binary search trees

A BST adds an ordering invariant: everything left is smaller, everything right is larger. That turns search into binary search over a structure that also supports O(log n) insertion — provided it stays balanced. It does not stay balanced on its own, and inserting sorted data produces a linked list, which is why real libraries use red-black or AVL trees.

What a BST gives you over a hash map: ordered iteration, range queries, and "nearest value above x". What it costs: O(log n) instead of O(1) per lookup.

What to say in the interview

Say which traversal you are using and why before writing it, and if the answer composes from subtrees, say "this is bottom-up — each call returns a summary". Give the cost as O(n) time and O(h) space, then immediately say what h is: log n balanced, n skewed. That last clause is the one interviewers wait for.

Where candidates slip

Missing the null base case. Every recursive tree function starts with the empty check; without it the first leaf's child crashes the call.
Assuming a BST is balanced. Inserting sorted values builds a linked list with extra steps, turning every O(log n) claim into O(n).
Validating a BST by comparing only against the parent. The property is about ranges — each node must fall inside a (low, high) window carried down from its ancestors.
Recursing on a deep tree without thinking about the stack. A skewed tree of 10⁵ nodes overflows the default limits in most languages.
Using DFS for shortest path. Depth-first finds a path; only breadth-first finds the shortest one in an unweighted graph or tree.

Possible follow-up questions

4 questions·try answering before you reveal