Question Bank
Tree Traversal Challenge
Difficulty: Medium
Five mid-level prompts on in-order, pre-order, post-order, and level-order traversal. Code-anchored with one trace and one bug hunt.
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.
940 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.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.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.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.