## Question Design a reusable tree-traversal library that supports preorder, inorder, postorder, and level-order traversal. Callers supply their own action for each visited node, may stop early, and may choose lazy iteration for trees too large to process eagerly. Discuss how parallel traversal could fit without making unsafe guarantees. ### Constraints & Assumptions - The initial structure is a binary tree, but the public design should not hard-code a particular node payload type. - Traversal order must be deterministic in sequential mode. - A caller action may request either continue or stop. - Lazy iterators should use space proportional to traversal frontier or height, not materialize all nodes. - Parallel callbacks cannot be assumed thread-safe. ### Clarifying Questions to Ask - Should mutation during traversal be supported? No; document that structural mutation is undefined or prohibited. - Does early stop need to return a result? The stop signal may carry an optional result. - Must one object support every traversal order? Prefer composable strategies behind one small interface. - Is parallel order deterministic? Not unless an explicit ordered merge is requested. ```hint Separate movement from action A traversal strategy decides which node comes next; a visitor or iterator consumer decides what to do with that node. ``` ### What a Strong Answer Covers - Generic node access, traversal strategies, visitor callbacks, and a clear early-stop result. - Iterative stack or queue state for each lazy order, especially inorder. - Reentrancy and avoidance of mutable traversal state shared across requests. - Extension points that do not require editing existing strategies. - Honest parallel semantics, cancellation, callback thread-safety, and ordering trade-offs. ### Follow-up Questions 1. Sketch the state machine for a lazy inorder iterator. 2. How would exceptions from a visitor be propagated and cleaned up? 3. Which traversal orders can be parallelized while preserving useful ordering?