dsa · medium

Binary Search Tree Iterator

Implement an iterator over a binary search tree that yields nodes in **inorder**: left subtree, then the node, then the right subtree.

Trees arrive as nested lists [val, left, right]. null is a missing child. The example tree is:

`` 7 / \ 3 15 / \ 9 20 ``

Inorder is 3, 7, 9, 15, 20.

Methods

• BSTIterator(root) start just before the smallest node. root is the tree, or null if empty
• next() return the next inorder value and advance. Only called when hasNext() is true
• hasNext() true while a later next() would still return a node

Example

The first inorder visit is the leftmost 3.

`` BSTIterator(tree) → null constructor; next value is 3 next() → 3 leftmost next() → 7 the root hasNext() → true next() → 9 hasNext() → true ``

Two more next() calls yield 15 then 20; hasNext() is then false.

Fill in the BSTIterator class. The starter already walks ops / args and calls your methods — leave the driver at the bottom as-is. Constructors contribute null; booleans print as true / false.

Constraints

1 <= nodes <= 100. next is only called when hasNext is true.

Examples

Example 1

Input:
["BSTIterator","next","next","hasNext","next","hasNext"]
[[[7,[3,None,None],[15,[9,None,None],[20,None,None]]]],[],[],[],[],[]]

Expected:
[null,3,7,true,9,true]

Open in the Dojo editor