BST Iterator Problem Statement

You are tasked with creating a class named BSTIterator that acts as an iterator for the inorder traversal of a binary search tree. Implement the following functions:

  1. BSTIterator(Node root): A constructor that inputs the root of the binary search tree and initializes the iterator.
  2. next(): Returns the next smallest element from the inorder traversal of the tree.
  3. hasNext(): Returns true if there remains a next element in the inorder traversal; otherwise, returns false.

Assume the binary search tree contains 'N' nodes, and you must print its inorder traversal using the iterator.

Input:

The first line of the input includes an integer T representing the number of test cases.
Each test case consists of a single line with nodes in level order form, where -1 indicates a null node.
For example, the input corresponds to a tree:

tree diagram

4
2 6
1 3 5 7
-1 -1 -1 -1 -1 -1

Output:

Output for each test case should be a line containing the inorder traversal of the binary search tree.

Example:

Input:
4 2 6 1 3 5 7 -1 -1 -1 -1 -1 -1
Output:
1 2 3 4 5 6 7

Explanation:

Level 1:
The root node of the tree is 4

Level 2:
Left child of 4 = 2
Right child of 4 = 6

Level 3:
Left child of 2 = 1
Right child of 2 = 3
Left child of 6 = 5
Right child of 6 = 7

Level 4:
Each child node at this level is null (-1), and the input concludes with all null nodes.

The tree is traversed in inorder, hence the output is 1 2 3 4 5 6 7.

Constraints:

  • 1 <= T <= 10
  • 1 <= N <= 104
  • 1 <= A[i] <= 109
Note:
The input sequence is provided in a single line separated by spaces. Implementation of the given functions is sufficient as output is handled externally.
AnswerBot
1d

Implement a BSTIterator class for inorder traversal of a binary search tree.

  • Create a BSTIterator class with constructor, next, and hasNext functions.

  • Use a stack to simulate inorder traversal of the bi...read more

Help your peers!
Add answer anonymously...
Amazon Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter