Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Binary Search Tree Iterator (medium)

Problem Statement

Implement an iterator for the in-order traversal of a binary search tree (BST). That is, given a BST, we need to implement two functions:

bool hasNext(): Returns true if at least one element is left in the in-order traversal of the BST. int next(): Return the next element in the in-order traversal of the BST.

Example:

Given the following BST:

Here is the in-order traversal of this tree: [1, 4, 10, 14, 15, 19, 20]

Here is the expected output from the algorithm based on different calls:

hasNext() -> true

next() -> 1

next() -> 4

.....

.....

.....

Like the course? Get enrolled and start learning!
M

Martin Koh

· 2 years ago

We need to add a customized constructor to accept TreeNode of root in the given code sample.

public Solution(TreeNode root) {
    initialize(root);
  }
Shashwat Kumar

Shashwat Kumar

· 2 years ago

Even though we have a separate thread for processing traverseLeft for right subtree in next() function, it actually is still synchronous because it first checks if all threads have been processed by calling checkThread and then only creates a new thread.