Coding interviews
Reveal answer and reasoning
For a mutable caller-owned tree, a copying snapshot offers simple repeatable traversal at O(n) upfront cost. A no-mutation precondition avoids that copy but transfers responsibility to callers. An API should not silently claim both snapshot behavior and allocation-free traversal when it implements neither synchronization nor copying.
Every node is pushed and popped once, so traversal takes O(n) time and O(h) auxiliary stack space, where h is tree height. A skewed tree makes h equal n. Producing a materialized output array would add O(n) result storage; this iterator itself yields values incrementally. Calling an iterative traversal constant-space merely because it avoids recursion ignores the explicit stack. A cycle can cause an infinite descent, and mutation during lazy enumeration changes what the consumer sees.
This sample deliberately relies on an owned immutable node fixture.
A rigorous explanation states the left-node-right order, describes the pending-ancestor invariant and gives a linear visit-count argument. It qualifies the sorted-output claim with the BST assumption and the space claim with tree height. The sample's empty-tree count checks termination without requiring a fabricated root. When reviewing a lazy API, also identify when enumeration starts and who may mutate the source before or during it.
These ownership questions are the practical interview extension beyond the earlier algorithms course's explicit-stack traversal mechanics. A partially consumed traversal should also be disposed by its consumer. The stack holds node references until that enumerator is finished or released, so streaming does not make retained source objects disappear immediately.
What a strong answer covers
- For a mutable caller-owned tree, a copying snapshot offers simple repeatable traversal at O(n) upfront cost.
- Every node is pushed and popped once, so traversal takes O(n) time and O(h) auxiliary stack space, where h is tree height.
- Calling an iterative traversal constant-space merely because it avoids recursion ignores the explicit stack.
Common pitfall
Calling an iterative traversal constant-space merely because it avoids recursion ignores the explicit stack. A cycle can cause an infinite descent, and mutation during lazy enumeration changes what the consumer sees. This sample deliberately relies on an owned immutable node fixture.
Follow-up questions
- Build a left-skewed three-node tree and trace the maximum stack size. Hint: record pending ancestors before the first yield. Then use a non-BST tree to show that inorder traversal alone does not guarantee sorted values.
- Would the same traversal be correct for a DAG with a shared child, and what would a visited set change?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.