How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Apple.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Apple during technical interviews.

Implement a lazy inorder traversal iterator

Quick Overview

This question evaluates understanding of binary tree traversal and iterator design, specifically the implementation of a lazy inorder iterator under target space and amortized time constraints; it belongs to the Coding & Algorithms category and emphasizes practical implementation skills.

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Design an **iterator** over a binary tree that returns nodes in **inorder** sequence (**left → root → right**) using **lazy traversal** (i.e., you may not precompute/store the entire inorder list). ### Interface Implement a class with the following operations: - `InorderIterator(root)`: initialize the iterator for the given binary tree root. - `boolean hasNext()`: returns `true` if there is a next node in inorder order. - `TreeNode next()`: returns the next node (or its value) in inorder order. ### Constraints / Goals - Must be lazy (no full traversal stored up-front). - Target space: `O(h)` where `h` is the tree height. - Target time: amortized `O(1)` per `next()`. ### Follow-up - If **multiple iterators** traverse the **same tree concurrently**, what assumptions and design choices are needed to ensure thread safety?

Quick Answer: This question evaluates understanding of binary tree traversal and iterator design, specifically the implementation of a lazy inorder iterator under target space and amortized time constraints; it belongs to the Coding & Algorithms category and emphasizes practical implementation skills.

Design a lazy inorder iterator for a binary tree. The iterator must return values in inorder order: left -> root -> right. You may not precompute and store the full inorder traversal up front. Because this judge expects a function, implement the iterator logic inside `solution(tree_values, operations)`. The function should: 1. Build the binary tree from a level-order list with `None` for missing children. 2. Initialize an inorder iterator for that tree. 3. Execute each operation in `operations`, where each operation is either `"hasNext"` or `"next"`. 4. Return a list of results in the same order as the operations. For this problem, `next()` should return the next node's value, not the node object itself. Your iterator should be lazy, use only O(h) extra space for traversal state (where h is the tree height), and support amortized O(1) time per `next()`. Follow-up discussion (not graded): If multiple iterators traverse the same tree concurrently, thread safety is easiest if the tree is immutable and each iterator keeps its own independent stack. If the tree can be modified while iterators are running, you need synchronization or snapshot/persistent-tree semantics.

Constraints

0 <= len(tree_values) <= 100000
Each non-None tree value is an integer in the range [-10^9, 10^9]
0 <= len(operations) <= 200000
Every `next` operation is valid: it is never called when the iterator is exhausted
Do not precompute the full inorder traversal; target auxiliary iterator space is O(h)

Examples

Input: ([4, 2, 6, 1, 3, 5, 7], ['hasNext', 'next', 'hasNext', 'next', 'next', 'next', 'next', 'next', 'next', 'hasNext'])

Expected Output: [True, 1, True, 2, 3, 4, 5, 6, 7, False]

Explanation: The inorder traversal of the tree is [1, 2, 3, 4, 5, 6, 7]. `hasNext` does not consume elements.

Input: ([], ['hasNext', 'hasNext'])

Expected Output: [False, False]

Explanation: An empty tree has no inorder values, so `hasNext` is always False.

Input: ([1, None, 2, 3], ['next', 'next', 'next', 'hasNext'])

Expected Output: [1, 3, 2, False]

Explanation: The tree has root 1, right child 2, and 2 has left child 3. Its inorder traversal is [1, 3, 2].

Input: ([5, 3, 7, 3, 4, None, 7], ['next', 'next', 'next', 'next', 'next', 'next'])

Expected Output: [3, 3, 4, 5, 7, 7]

Explanation: This verifies correct lazy traversal when duplicate values appear in the tree.

Hints

Store only the path of nodes that could produce the next inorder value. A stack is useful here.
After returning a node, the next inorder value comes from the leftmost path of its right subtree.

Quick Overview