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)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible