FastPrepLazy Binary Tree Inorder Iterator
Problems/Lazy Binary Tree Inorder Iterator

Lazy Binary Tree Inorder Iterator

Apple logoApple● MediumNEW GRADPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in an Apple new grad phone screen. The report describes a lazy inorder iterator, its time and space goals, and a follow-up about concurrency. It did not share how to send operations in a batch, the examples, or the numeric limits. We chose those. Our version is about 95% the same as the reported question.

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"]
root
7315920

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"]
root
291

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)
All Apple interview questionsSee Apple hiring insights
Saved
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public String[] runInorderIterator(TreeNode root, String[] operations) {
        // Write your solution here.
    }
}
Checking account…