Trees and Traversals

1The mental model (what this really is)#

Start with the definition, then the one shift that makes everything click.

What a tree is.

• Nodes where each points to some children and has exactly one parent (the root has none).
• No cycles. That is the whole definition.
• A binary tree is the special case: each node has at most two children, left and right.

The shift: a tree is defined in terms of itself.

• The left child of the root is itself the root of a smaller tree. So is the right child.
• Every node you land on, treat as the root of its own subtree and ask the same question you asked at the top.
• That self-similarity is why recursion fits trees like a glove: write code for one node, assume it works for the children, and the structure handles the rest.

Traversal means visiting every node in some order. There are only two families:

• Depth first: go deep down one path before backing up. Natural with recursion.
• Breadth first: visit everything one level at a time, top to bottom. Natural with a queue.

Learn those two shapes cold and you derive the rest live. Better to deeply own two patterns than half-remember ten.

2How to recognize it (the signals in a problem)#

Spot the shape fast and you start thinking recursion before the interviewer finishes the prompt.

You are looking at a tree problem when:

• The input is a TreeNode root, or a hierarchy: an org chart, a file system, nested comments, a DOM, a decision tree.
• The prompt uses words like "subtree," "ancestor," "depth," "level," "path from root," or "parent." Dead giveaway.

Pick the family by what the question asks:

• "Level by level," "left to right per row," "shortest number of steps," "closest" points to breadth first (BFS).
• "Path," "depth," "sum along a branch," "is this a valid X," "compare two subtrees," anything recursive-sounding points to depth first (DFS).
• Sorted output from a BST, "kth smallest," or "validate BST" points to DFS with inorder specifically.

3The template (how it works, with pseudocode)#

Three templates cover the vast majority of what you will be asked. Burn them in so you can write them without thinking and spend your brain on the actual problem.

DFS, recursive. Your default. Decide what you do before, between, and after the child calls.

def dfs(node):
 if node is None:
 return base_case # empty subtree: 0, True, null, etc.

 left = dfs(node.left)
 right = dfs(node.right)

 # combine results of children with this node's value
 return combine(node.val, left, right)

The three classic DFS orders are just where you "visit" the node relative to the recursive calls:

preorder: visit node, then left, then right # root first
inorder: left, visit node, then right # sorted order in a BST
postorder: left, right, then visit node # children before parent

BFS, level order. Use a queue. The trick most people miss: snapshot the queue size at the start of each level so you know exactly how many nodes belong to that row.

def bfs(root):
 if root is None: return []
 queue = [root]
 result = []
 while queue:
 level_size = len(queue) # <-- freeze this row's count
 level = []
 for _ in range(level_size):
 node = queue.pop_front()
 level.append(node.val)
 if node.left: queue.push(node.left)
 if node.right: queue.push(node.right)
 result.append(level)
 return result

DFS, iterative with an explicit stack. Keep it in your back pocket. For when the interviewer says "now do it without recursion." Senior and staff loops will ask, because they want to see you understand recursion is just a stack the language manages for you.

def iterative_preorder(root):
 if root is None: return
 stack = [root]
 while stack:
 node = stack.pop()
 visit(node)
 if node.right: stack.push(node.right) # push right first
 if node.left: stack.push(node.left) # so left pops first

4A worked example (walk through one problem step by step)#

Take Maximum Depth of a Binary Tree, because the way you think about it is the way you should think about half of all tree problems.

The question. Return the number of nodes along the longest path from the root down to the farthest leaf.

Imagine this tree:

 3
 / \
 9 20
 / \
 15 7

The answer is 3: the path 3 -> 20 -> 15 (or 3 -> 20 -> 7).

The reasoning. Forget the whole tree. Stand on one node and ask: "If I already knew the depth of my left subtree and my right subtree, how would I compute my own depth?" Easy. My depth is 1 (for myself) plus the deeper of my two children.

depth(node) = 1 + max(depth(node.left), depth(node.right))

The base case is the empty tree. An empty subtree has depth 0. That is what stops the recursion.

def max_depth(node):
 if node is None:
 return 0
 return 1 + max(max_depth(node.left), max_depth(node.right))

Walk it top down, let it unwind bottom up:

1. Call on 3. It needs the depth of 9 and of 20.
2. Call on 9. Both its children are empty. So 1 + max(0, 0) = 1. Node 9 reports back 1.
3. Call on 20. It needs 15 and 7.
4. Call on 15. Empty children, reports 1 + max(0, 0) = 1. Same for 7: reports 1.
5. Back at 20: 1 + max(1, 1) = 2. Node 20 reports 2.
6. Back at 3: 1 + max(1, 2) = 3. Done.

Why this one example teaches half the topic.

• You never thought about the tree as a whole. You wrote the rule for one node and trusted recursion for the other four.
• This is a postorder pattern: you need both children's answers before computing your own, so you "visit" yourself last.
• That "children first, then me" shape powers a huge number of problems: subtree sums, balanced-tree checks, diameter, counting nodes.
• See one, you see them all. That is the payoff of learning the shape instead of the code.

5Variations and gotchas#

The template rarely arrives unchanged. These are the twists interviewers throw and how to catch each one.

Inorder on a BST gives sorted order, for free.

• Kth smallest in a BST, or validate a tree is a BST: do an inorder traversal and values come out ascending.
• For validation, check each value is strictly greater than the previous one you saw.
• This is the single highest-leverage fact about BSTs in interviews.

Carrying state down vs bubbling up. Two distinct recursion styles, and naming which one you use out loud buys credibility:

• Pass data down as a parameter (a running path sum, or a valid value range). Good for "path from root" and BST validation.
• Return data up from children and combine it. Good for depth, counts, subtree properties.
• Decide the direction out loud before you write a line. Picking wrong is the most common reason a candidate rewrites a solution twice.

Morris traversal does inorder in O(1) extra space by temporarily rewiring pointers back to predecessors.

• A nice flex for a senior round, but do not open with it.
• Get the clean O(h)-space version working first, then mention Morris as the optimization if they push on space.

N-ary trees just swap left and right for a children list.

• Your DFS loops over node.children instead of calling on two fixed fields.
• Same idea, same complexity.

Serialize and deserialize is a tree favorite, and a common hard round at Meta.

• Preorder with explicit null markers is the cleanest encoding: write the root, then recursively serialize left and right, emitting a sentinel like # for null.
• Deserialization reads the stream back in the same preorder.
• It is really just a traversal with record-and-rebuild bolted on.

6Complexity#

For any single traversal that touches every node once, the time is settled and the space is where points are won or lost.

Time: O(n), where n is the number of nodes.

• You cannot do better for a full traversal. You have to look at everything at least once.

Space: O(h), where h is the height, for the stack. Not O(n).

• At any moment you only have one root-to-current-node path sitting on the call stack.
• Nodes you already finished have returned and popped off. That live path is at most the height.

How h behaves:

• Balanced tree: h is about log n, so space is O(log n). For a million nodes, roughly 20 frames.
• Skewed tree (basically a linked list leaning one way): h equals n, so space degrades to O(n). This is also where you blow the recursion limit and get a stack overflow, which is exactly why interviewers ask for the iterative version. Python caps recursion depth near 1000 by default, so a 10,000-node skewed tree crashes a naive recursive solution.

BFS space is O(w), the maximum width of the tree.

• For a full bottom level, width can be up to n/2, so call it O(n) in the worst case.
• That is the honest answer to "which is more memory-hungry, DFS or BFS": DFS costs the height, BFS costs the width.

7Mistakes that cost people the round#

Every one of these is a quiet failure: correct-looking code that burns five minutes or returns garbage under the clock.

Forgetting the null check.

• The single most common crash. Every recursive tree function starts with if node is None.
• Write that line first, before anything else, every single time. Muscle memory.

Reaching for loops when recursion is the answer.

• Strong engineers try to flatten a tree with nested for loops and tie themselves in knots for ten minutes.
• If the structure is recursive, let the recursion carry the context instead of rebuilding it by hand.

Using the wrong traversal order.

• Ask for sorted BST output with a preorder and you get garbage and will not know why.
• You will burn five minutes debugging a correct implementation of the wrong algorithm.
• Match the order to the job: inorder for sorted, postorder for children-before-parent, preorder for root-first encodings, BFS for levels.

Mutating shared state carelessly.

• When you pass a path list down and append to it, you must remove the element on the way back up (backtrack).
• Forget the pop after the recursive calls and the sibling branch inherits junk from the branch you just finished.
• Wrong answers that are brutal to debug under a clock.

Losing the level boundary in BFS.

• Forget to freeze level_size before the inner loop and the loop keeps consuming nodes you pushed this level.
• All rows merge into one soup. Snapshot the count first, then drain exactly that many.

Ignoring the skewed-tree case.

• When they ask about complexity, say O(h) and immediately name the worst case where h equals n.
• It shows you understand why it is h and not n, and the skewed case is very often the follow-up they were fishing for.

8Your practice path (named problems by difficulty)#

Do them in roughly this order. The point is to feel the same three templates stretch to fit new shapes, not to grind volume.

Warm up (Easy):

• Maximum Depth of Binary Tree
• Invert Binary Tree
• Same Tree
• Symmetric Tree
• Path Sum
• Diameter of Binary Tree

Build the core (Medium):

• Binary Tree Level Order Traversal
• Binary Tree Zigzag Level Order Traversal
• Validate Binary Search Tree
• Kth Smallest Element in a BST
• Lowest Common Ancestor of a Binary Tree
• Construct Binary Tree from Preorder and Inorder Traversal
• Binary Tree Right Side View
• Count Good Nodes in Binary Tree
• Flatten Binary Tree to Linked List

Sharpen (Hard):

• Binary Tree Maximum Path Sum
• Serialize and Deserialize Binary Tree
• Vertical Order Traversal of a Binary Tree
• Recover Binary Search Tree

If you only do five, do these: Maximum Depth, Level Order Traversal, Validate BST, Lowest Common Ancestor, and Binary Tree Maximum Path Sum. They hit every pattern you need:

• Bubbling results up (Maximum Depth).
• BFS by level (Level Order Traversal).
• Inorder on a BST (Validate BST).
• Carrying context down to find a split point (Lowest Common Ancestor).
• The global-vs-return-value trick in Max Path Sum that trips up almost everyone the first time.

Own two traversal shapes cold, and you can derive the other ten live.

9Where this shows up#

Trees are table stakes at every big tech company.

• Google, Meta, Amazon, and Microsoft all lean hard on them in standard coding rounds, often as the warm-up before a graph problem (which is really just a tree that allows cycles).
• Amazon loves BST and level-order variants.
• Meta is fond of lowest common ancestor and serialize/deserialize.
• Senior and staff loops almost always push you to the iterative version and grill you on space complexity, so do not stop at the recursive solution.
• Getting the recursive answer fast and then calmly converting it to an explicit stack is exactly the signal that separates a Medium pass from a strong Senior yes.

Want to see which rounds at which companies lean on this? Check the company guides to map the pattern to real interview loops.