Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Binary Search Tree Iterator (medium)
On this page

Problem Statement

Try it yourself

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:

Image

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

hasNext() -> true

next() -> 10

next() -> 14

next() -> 15

next() -> 19

next() -> 20

hasNext() -> false

Constraints:

  • The number of nodes in the tree is in the range [1, 10<sup>5</sup>].
  • 0 <= Node.val <= 10<sup>6</sup>
  • At most 105 calls will be made to hasNext, and next.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page

Problem Statement

Try it yourself