Lazy Binary Tree Inorder Iterator
Updated
Problem statement
Implement a lazy inorder iterator for a read-only binary tree. Inorder means visit the left subtree, then the node, then the right subtree. The tree does not have to be a binary search tree.
For the executable task, create one iterator at root and process operations in order:
HAS_NEXT: return the string"true"if an unvisited node remains, otherwise"false". This operation does not advance the iterator.NEXT: advance to the next inorder node and return its value as a decimal string.
Return one string for every operation. Every NEXT call is valid. Use O(h) auxiliary iterator state, where h is the tree height; do not store the full traversal. After O(h) initialization, HAS_NEXT must take O(1) time and NEXT must take amortized O(1) time. The returned output array is separate from iterator state.
Follow up: explain why separate iterators can share a read-only tree. What synchronization or snapshot rules would be needed if the tree could be changed?
Function
runInorderIterator(root: TreeNode, operations: String[]) → String[]Examples
Example 1
root = [7,3,15,null,null,9,20]operations = ["HAS_NEXT","NEXT","NEXT","HAS_NEXT","NEXT","NEXT","NEXT","HAS_NEXT"]return = ["true","3","7","true","9","15","20","false"]The inorder values are [3,7,9,15,20]. The first two NEXT calls return 3 and 7; nodes remain at the next check. The last three NEXT calls return 9, 15, and 20, after which HAS_NEXT returns "false".
Example 2
root = [2,9,1]operations = ["NEXT","HAS_NEXT","HAS_NEXT","NEXT","NEXT","HAS_NEXT"]return = ["9","true","true","2","1","false"]Inorder follows tree structure, so the values are [9,2,1]. Both repeated HAS_NEXT calls return "true" without consuming node 2.
Constraints
- root is a valid binary tree with 0 through 10^4 nodes.
- Every node value is between -10^4 and 10^4, inclusive.
- 0 <= operations.length <= 2 * 10^4.
- Every operation is NEXT or HAS_NEXT.
- The number of NEXT operations is at most the number of nodes.
More Apple Phone Screen questions
- Subarray Product Less Than KPHONE SCREEN · Seen Nov 2026
- Evaluate DivisionPHONE SCREEN · Seen Nov 2026
- Reverse a Linked ListPHONE SCREEN · Seen Nov 2026
- Validate a BST with a Custom ComparisonPHONE SCREEN · Seen Nov 2026
- Design a Food Rating SystemPHONE SCREEN · Seen Oct 2026
- Days Until Poisoned Plants StabilizePHONE SCREEN · Seen Oct 2026
- Capture Surrounded Regions with Union-FindPHONE SCREEN · Seen Oct 2026
- Maintain a Consistent-Hashing RingPHONE SCREEN · Seen Oct 2026
- Count Nodes in a ChainPHONE SCREEN · Seen Oct 2026
- Run-Length DecodingPHONE SCREEN · Seen Oct 2026
Similar questions at other companies
- Binary Search Tree IteratorAtlassian · OAAtlassian interview questions
- Evaluate an Addition and Subtraction TreeExpedia · ONSITE INTERVIEWExpedia interview questions
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
- Top K Pins with Insert and QueryPinterest · PHONE SCREENPinterest interview questions
- Tree Selection and VisibilityJane Street · PHONE SCREENJane Street interview questions
- Billing Log with Undo and RedoReddit · PHONE SCREENReddit interview questions
- KV Store with Nested TransactionsApplied Intuition · PHONE SCREEN · ONSITE INTERVIEWApplied Intuition interview questions
- Worst-Performing Ads by CTR in a Campaign TreeUber · PHONE SCREENUber interview questions
- Search for an Element in a StreamAmazon · PHONE SCREEN
Apple interview experiences
- Apple SWE Phone Screen: Subarray Products: 1 Experience
- Apple New Grad SWE Java, Coding and Manager Rounds: 1 Experience
- Apple AI Coding and Related Interviews: 17 Experiences
- Apple India SWE New Grad Interviews: 5 Experiences
- Apple New Grad SWE Phone Screens: 12 Experiences (Part 3 of 3)
- Apple New Grad SWE and Embedded: 16 Experiences (Part 2 of 3)