The Four Traversals
Binary tree traversals: Inorder (left, root, right) — gives sorted order for a BST. Preorder (root, left, right) — useful for copying a tree, prefix expression. Postorder (left, right, root) — useful for deleting a tree, postfix expression. Level order (BFS) — visits nodes level by level, shortest-path style. Know both recursive and iterative implementations. Recursive is compact; iterative avoids stack overflow on deep trees and is often required in interviews.
def inorder(root):
result = []
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return resultLevel Order Traversal (BFS)
Process nodes level by level using a queue. Track level boundaries by processing the entire current queue size in one loop iteration (snapshotting the current level size).
from collections import deque
def level_order(root):
if not root: return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)): # process exactly one level
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return resultVariants: LC 103 Zigzag level order — alternate left-to-right and right-to-left. Use a deque: for odd levels append right, for even levels appendleft. LC 116 Populating Next Right Pointers — level order, set node.next for each node to the next node in the same level. LC 513 Find Bottom Left Value — return the first node of the last level.
Path Problems
LC 112 (Path Sum): DFS, subtract node value from remaining target. At leaf: check if remaining == 0. LC 113 (Path Sum II): DFS with a running path list. At leaf with remaining==0: append a copy to results. Pop after recursion (backtrack). LC 124 (Binary Tree Maximum Path Sum): at each node, compute max gain from left subtree and right subtree (max(0, left_gain) to ignore negative paths). Update global max with left_gain + node.val + right_gain. Return node.val + max(left_gain, right_gain) to the parent (can only go one direction in a path from the parent’s perspective). LC 543 (Diameter): same pattern — diameter through a node = left_depth + right_depth.
Lowest Common Ancestor (LC 236, 235)
LC 236 (general binary tree): DFS post-order. If current node == p or q, return it. Recurse left and right. If both return non-null: current node is the LCA. If one returns null: LCA is in the other subtree. LC 235 (BST): if both p and q are less than root, LCA is in left subtree. If both greater, right subtree. Otherwise, root is the LCA. O(h) time. For the general case, the post-order approach uses O(n) time and O(h) space (recursion stack).
Serialize and Deserialize Binary Tree (LC 297)
Preorder serialization: serialize = preorder DFS, write “#” for null. Deserialize: use a global index (or iterator) into the serialized array. At each call: if value is “#”, return None; else create a node and recurse for left and right children.
def serialize(root):
res = []
def dfs(node):
if not node: res.append("#"); return
res.append(str(node.val))
dfs(node.left); dfs(node.right)
dfs(root)
return ",".join(res)
def deserialize(data):
vals = iter(data.split(","))
def dfs():
v = next(vals)
if v == "#": return None
node = TreeNode(int(v))
node.left = dfs(); node.right = dfs()
return node
return dfs(){
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “Why does iterative inorder traversal use a stack and a current pointer instead of just a stack?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Recursive inorder: go left as far as possible, process root, go right. In the iterative version, the stack simulates the recursion stack. The current pointer (curr) represents the node we are about to explore — “the node we’d pass to the recursive call.” The inner while loop (while curr: stack.append(curr); curr = curr.left) descends to the leftmost node, pushing all ancestors. When we pop from the stack: this is the moment the recursive function would process the root (after returning from left subtree). We append curr.val and then move to curr.right to explore the right subtree. Without the current pointer, we’d lose track of where to go after popping — the pointer cleanly separates “exploring the left path” (pushing) from “processing and moving right” (popping). This pattern generalizes: the stack handles “pending” ancestors; the pointer handles the current descent.”
}
},
{
“@type”: “Question”,
“name”: “How do you find the right answer for the binary tree maximum path sum problem (LC 124)?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Key insight: a path in a binary tree can go through any node as its “peak.” At each node, the maximum path through that node = left_gain + node.val + right_gain, where left_gain = max(0, max_gain(left child)) and right_gain = max(0, max_gain(right child)). Taking max(0, …) handles negative subtrees by not extending into them. The function returns node.val + max(left_gain, right_gain) to the parent — because from the parent’s perspective, the path can only come up through one side (cannot fork). The global maximum is updated inside the recursive function as we process each node as the potential peak. Common mistake: returning left_gain + node.val + right_gain to the parent — this would allow the path to fork, which is invalid. Return only the better of the two sides to the parent; track the full path value as a side effect.”
}
},
{
“@type”: “Question”,
“name”: “What is the difference between lowest common ancestor in a general binary tree vs a BST?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “BST (LC 235): exploit the ordering property. If both p and q are less than root.val, the LCA must be in the left subtree (recurse left). If both are greater, recurse right. Otherwise, root is the LCA (p and q straddle the root). O(h) time, O(h) space (recursion). This is clean and fast because we can eliminate half the tree at each step without visiting child nodes. General binary tree (LC 236): no ordering to exploit — must search both subtrees. Post-order DFS: recurse left and right, then check: if left result is non-null AND right result is non-null, the current node is the LCA (p and q are in different subtrees). If only one side is non-null, propagate that result upward. Base cases: if current node == p or == q, return it. Time: O(n) — must visit every node. Space: O(h) for recursion stack. For the BST version, never write O(n) DFS when the BST property gives you O(h).”
}
},
{
“@type”: “Question”,
“name”: “How does the serialization/deserialization approach work and why does preorder work better than inorder?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Preorder serialization encodes the tree structure unambiguously: root first, then left subtree, then right subtree, with null markers (#). Deserialization uses a single pass through the serialized values with an iterator — at each step, pop one value: if #, return None; otherwise create a node and recurse for left and right. The key property: in preorder, the root always appears before its subtrees, so the deserializer knows what to create before recursing into children. Inorder serialization (left, root, right) is ambiguous for general binary trees — without explicit null markers AND knowing the preorder, you cannot reconstruct the tree. (Inorder alone doesn’t tell you where the root is.) Preorder with null markers IS unambiguous: each subtree’s structure is fully determined by its own preorder sequence starting with the root. Level-order (BFS) serialization is also unambiguous and is what LeetCode uses for its tree representation.”
}
},
{
“@type”: “Question”,
“name”: “How do you handle zigzag level order traversal efficiently?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Zigzag: even-numbered levels go left-to-right, odd-numbered levels go right-to-left. Two approaches: (1) Deque per level: collect the current level’s values into a deque. For left-to-right levels: append to the right. For right-to-left levels: appendleft. At the end of each level, convert the deque to a list. This avoids reversing. (2) Collect normally then reverse: collect the full level into a list (same as standard level order), then reverse the list for odd levels (result.append(level[::-1])). Both are O(n) total. The deque approach avoids the extra allocation from slicing but is marginally more complex. In practice, either works in an interview. The pattern to memorize: track level_index (or use a boolean left_to_right). Toggle the direction after each level. The BFS queue structure is identical to standard level order — only the insertion direction into the result changes.”
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Atlassian Interview Guide