Tree Traversal Challenge
Five mid-level prompts on in-order, pre-order, post-order, and level-order traversal. Code-anchored with one trace and one bug hunt.
941 views
22
Implement inorder(root) returning the in-order traversal of a binary tree as an array of values. Use either recursion or an explicit stack.
Examples
Example 1:
Input: BST 4 -> (2 -> (1, 3), 6 -> (5, 7))
Output: [1, 2, 3, 4, 5, 6, 7]
Explanation: In-order visits left subtree, node, right subtree. Iterative version pushes ancestors onto a stack while diving left, then pops, records the value, and dives into the right child. O(n) time, O(h) stack.function inorder(root) {
// TODO: left, node, right
}Implement levelOrder(root) returning a 2D array where each inner array holds the node values at one depth. Use a BFS with a queue.
Examples
Example 1:
Input: tree 3 -> (9, 20 -> (15, 7))
Output: [[3], [9, 20], [15, 7]]
Explanation: Queue-based BFS. While the queue is non-empty, capture the current level size n, dequeue exactly n nodes, push their values to a row, and enqueue their non-null children. O(n) time, O(width) space.function levelOrder(root) {
// TODO: BFS that records one row per level
}Trace it. For the tree 1 -> (2 -> (4, 5), 3) (root 1, left child 2 with children 4 and 5, right child 3), give the pre-order, in-order, post-order, and level-order traversals.
Implement maxDepth(root) returning the height (number of nodes on the longest root-to-leaf path). Use whichever traversal you prefer.
Examples
Example 1:
Input: tree 3 -> (9, 20 -> (15, 7))
Output: 3
Explanation: depth(null) = 0; depth(node) = 1 + max(depth(left), depth(right)). Recursive post-order: visit children, then combine. O(n) time, O(h) stack.function maxDepth(root) {
// TODO: recursive depth
}Spot the bug. This iterative pre-order is supposed to return root values in pre-order. It returns post-order-like values for some trees.
Examples
Example 1:
Input: tree 1 -> (2, 3)
Output (buggy version): [1, 3, 2]
Output (fixed version): [1, 2, 3]
Explanation: A stack pops LIFO, so to visit the left child first we must push the right child first, then the left. The buggy version pushes left first, so the left subtree is processed after the right subtree.function preorder(root) {
if (!root) return [];
const out = [], stack = [root];
while (stack.length) {
const node = stack.pop();
out.push(node.val);
if (node.left) stack.push(node.left);
if (node.right) stack.push(node.right);
}
return out;
}