Tree Traversal Fundamentals
Binary tree problems appear in nearly every technical interview. The foundation is traversal order, which determines which problems you can solve recursively versus iteratively.
- Inorder (Left → Root → Right): produces sorted output for a BST. Used for BST validation, kth-smallest, BST iterator, and converting BST to sorted array.
- Preorder (Root → Left → Right): root processed before children. Used for tree serialization, path sum problems, and building a copy of the tree.
- Postorder (Left → Right → Root): children processed before root. Used when you need information from subtrees to compute the root’s answer — subtree sums, tree height, balanced tree check, delete nodes.
- Level-order (BFS): process level by level using a queue. Used for right side view, zigzag traversal, max level sum, and populating next right pointers.
The DFS Recursive Template
Most tree problems fit one of two DFS patterns:
Pattern 1 — Return value from subtree (bottom-up): the recursive function computes something for each subtree and returns it to the parent. Use this when each node’s answer depends on its children’s answers.
def solve(node):
if not node:
return base_case
left = solve(node.left)
right = solve(node.right)
return combine(left, right, node.val)
Examples: tree height (return 1 + max(left, right)), diameter of binary tree (update global max with left+right, return 1+max(left,right)), check balanced tree.
Pattern 2 — Pass state down (top-down): pass accumulated information from parent to children. Use when each node needs context from its ancestors.
def solve(node, state):
if not node:
return
# use node.val and state
solve(node.left, new_state)
solve(node.right, new_state)
Examples: path sum (pass remaining target down), all root-to-leaf paths (pass current path), max path sum to leaf.
Classic Problems by Pattern
Height / Depth (postorder, return value): maximum depth is the canonical example. Minimum depth requires handling the case where a node has only one child — a node with one child is NOT a leaf, so minimum depth = 1 + min of the non-null child.
Diameter of Binary Tree: the diameter is the longest path between any two nodes, which may or may not pass through the root. At each node, the longest path through that node = height(left) + height(right). Track a global maximum. Return 1 + max(height(left), height(right)) for the parent. Time O(n).
Balanced Binary Tree: a tree is balanced if, for every node, |height(left) – height(right)| ≤ 1. Combine height computation and balance check in one DFS: return -1 to propagate “unbalanced” upward (early termination), else return the actual height. Time O(n) versus the naive O(n log n) solution that calls height separately.
Lowest Common Ancestor (LCA): if both target nodes are in the left subtree, recurse left. If both are in right, recurse right. If they’re on different sides (or one is the current node), the current node is the LCA. Base case: null returns null; finding either target returns the target itself. Time O(n).
Serialize and Deserialize Binary Tree: preorder traversal with null markers. Serialize: if null, append “#”; else append val and recurse left then right. Deserialize: use a queue of tokens; dequeue one token — if “#”, return null; else create a node and set left = deserialize(), right = deserialize(). Time and space O(n).
BST-Specific Problems
BST invariant: left subtree values < root < right subtree values. Inorder traversal of a BST is always sorted.
Validate BST: pass a (min, max) range down the tree. At each node, check min < node.val < max. For the left child, the new max becomes node.val. For the right child, the new min becomes node.val. Initialize with (-∞, +∞). A common mistake: comparing only parent-child relationships (misses the constraint that ALL left subtree values must be less than root).
Kth Smallest in BST: inorder traversal is sorted ascending. Use a counter; decrement on each inorder visit; when counter reaches 0, record the current node. For frequent queries with insert/delete operations, augment the BST with a subtree_count at each node to enable O(log n) kth-smallest queries.
Convert Sorted Array to BST: always pick the middle element as root (ensures height-balanced). Recurse on left half for left subtree, right half for right subtree. Time O(n).
Level-Order (BFS) Problems
BFS uses a deque. Template:
from collections import deque
queue = deque([root])
while queue:
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
# process node
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
Right Side View: the last node processed in each level is the right-side visible node. Zigzag Traversal: alternate appending left-to-right and right-to-left — use a direction flag and a deque (appendleft vs append). Max Level Sum: track max sum across levels during BFS. Populating Next Right Pointers: O(1) space BFS using the already-assigned next pointers of the previous level as the queue — process level N using next pointers to traverse level N, and set next pointers for level N+1.
Iterative Traversal
Interviewers sometimes ask for iterative implementations to avoid stack overflow on deep trees:
Iterative inorder: maintain an explicit stack. Push all left children until hitting null. Pop a node, visit it, then push its right child. Repeat.
Iterative preorder: push root; while stack not empty: pop and visit, then push right, then push left (left is processed first since stack is LIFO).
Morris traversal: O(1) space inorder using threaded tree pointers — finds the inorder predecessor of each node and threads it. Avoids both recursion stack and explicit stack. Complex to implement but shows deep tree understanding in interviews.
Interview Tips
- Null check is your base case — always ask yourself what should be returned for a null node before writing recursive code.
- Identify if you need top-down (pass info down) or bottom-up (aggregate from children) — this determines parameter vs return value.
- Global variable trick: for problems where the answer spans the root (diameter, max path sum), use a nonlocal variable updated during the bottom-up DFS while the function returns a different value to the parent.
- When asked for iterative: translate the recursion stack to an explicit stack, pushing nodes in reverse visit order.
- BST problems: always think about whether the inorder property (sorted order) can be exploited.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the difference between tree depth-first search and breadth-first search for interview problems?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “DFS explores as deep as possible along one branch before backtracking. It uses a recursion stack (implicit) or explicit stack data structure. DFS has O(h) space complexity where h is tree height u2014 O(log n) for balanced trees, O(n) worst case for skewed trees. Use DFS when: you need information from subtrees to compute the parent’s answer (postorder bottom-up), you’re searching for a path from root to a node (preorder top-down), or you need to serialize/deserialize the tree. BFS explores all nodes at the current depth before going deeper. It uses a queue and O(w) space where w is the maximum tree width (can be O(n) for a complete binary tree’s last level). Use BFS when: you need to process nodes level by level, find the shortest path in an unweighted tree, compute level sums/averages, or get the right side view. The rule of thumb: if the problem mentions “level” or “depth by depth”, use BFS. If it mentions “path”, “subtree”, or “leaves”, use DFS.”
}
},
{
“@type”: “Question”,
“name”: “How do you find the Lowest Common Ancestor (LCA) of two nodes in a binary tree?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “LCA algorithm for a general binary tree (not BST): recursively search for both target nodes. At each node: if the node is null, return null. If the node equals target p or q, return the node itself (without searching further u2014 if the other target is a descendant, the current node is the LCA). Recursively get left = LCA(node.left, p, q) and right = LCA(node.right, p, q). If both left and right are non-null, the current node is the LCA (p and q are in different subtrees). If only one is non-null, return that non-null result. Time O(n), space O(h). For BST: exploit BST property u2014 if both p and q are less than current node, LCA is in left subtree; if both greater, right subtree; otherwise current node is the LCA (O(log n) for balanced BST). For a binary tree with parent pointers: follow parent pointers from p and q to root, find where the paths first meet u2014 equivalent to finding the intersection of two linked lists.”
}
},
{
“@type”: “Question”,
“name”: “How do you serialize and deserialize a binary tree and what traversal order should you use?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Preorder traversal with null markers is the standard approach. Serialization: recursively visit root first, then left, then right. If node is null, append a null marker (e.g., “#”). Otherwise append node.val. Result is a comma-separated string like “1,2,4,#,#,5,#,#,3,#,#”. Deserialization: split the string into a token list. Use a recursive function that reads one token at a time (using an index or iterator). If the token is “#”, return null. Otherwise, create a node with the token’s value, then set node.left = deserialize() and node.right = deserialize() u2014 the preorder structure guarantees root is always read before its children, enabling correct reconstruction. Time and space O(n). Why preorder and not inorder? Inorder traversal is ambiguous u2014 the same inorder sequence can represent multiple different trees. Preorder with null markers is unambiguous. Level-order (BFS) serialization (LeetCode tree representation) is also valid but slightly more complex to deserialize.”
}
}
]
}