Coding interviews
Reveal answer and reasoning
Traverse an acyclic binary tree in left-node-right order without recursion. The explicit stack stores ancestors whose left descent is in progress and whose node visit remains pending. The structure is assumed to be a tree rather than an arbitrary graph with shared or cyclic links. Sorted output follows only if the input also satisfies a binary-search-tree ordering rule. The stack is a record of deferred node visits, not a generic visited set.
Every time current moves left, the current node is saved because its own value and right subtree remain pending. When no further left node exists, popping selects exactly the next inorder node under the tree assumption.
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. Lazy output avoids storing the entire traversal result inside the iterator, but a consumer such as ToArray can add that storage afterward.
Stack growth follows height, not the number of already yielded nodes. This is why an iterative implementation avoids call-stack recursion limits without guaranteeing constant total memory.
What a strong answer covers
- Traverse an acyclic binary tree in left-node-right order without recursion.
- After yielding a node, setting current to its right child starts the same left-descent process for that subtree.
- Every node is pushed and popped once, so traversal takes O(n) time and O(h) auxiliary stack space, where h is tree height.
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.