Implement a lazy inorder traversal iterator

Q: Implement a lazy inorder traversal iterator

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

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?

Implement a lazy inorder traversal iterator

Quick Overview

Interface

Constraints / Goals

Follow-up

Comments (0)