Katkat
Back

Implement a lazy inorder traversal iterator

AppleSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to implement a binary tree iterator that performs inorder traversal using O(h) extra space, where h is the height of the tree, while maintaining an amortized time complexity of O(1) per call.

Problem Statement

Design an iterator class BSTIterator that represents an inorder traversal of a binary search tree (BST). The iterator should support the following operations:

  • BSTIterator(root): Initializes the iterator with the root node of a BST.
  • next(): Returns the next smallest element in the BST.
  • hasNext(): Returns true if there are still elements to traverse, otherwise returns false.

Constraints

  • The iterator should use O(h) space, where h is the tree height.
  • next() should operate in O(1) amortized time.
  • You may assume next() calls will always be valid if hasNext() returns true.

Example

Input:
root = [7, 3, 15, null, null, 9, 20]

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // returns 3
iterator.next();    // returns 7
iterator.hasNext(); // returns true
iterator.next();    // returns 9

Implementation Template

class BSTIterator:
    def __init__(self, root: TreeNode):
        pass

    def next(self) -> int:
        pass

    def hasNext(self) -> bool:
        pass

Hints

Hint 1

To achieve O(h) space, use a stack to keep track of the current path from the root to the smallest unvisited node.

Hint 2

In the constructor, pre-process the left-most branch by pushing all left children onto the stack.

Hint 3

When calling next(), pop the top element, then perform the same 'push all left children' logic on the right subtree of the popped node.

Follow-up questions

  • How would you modify your implementation if you were required to support reverse inorder traversal (traversing from largest to smallest)?
  • Can you implement this with O(1) space complexity if you are allowed to modify the tree structure (e.g., Morris Traversal)?
  • What are the implications of using this iterator in a multi-threaded environment where the tree might be modified concurrently?