#173

Binary Search Tree Iterator

pupil · 480 · lc medium +27 · 76.2% accepted · 9,196 likes · top 87%

Description

Implement the BSTIterator class that represents a cursor advancing through the in-order traversal of a binary search tree (BST):

- BSTIterator(TreeNode root) initializes the iterator. The cursor starts before the smallest element in the BST.

- boolean hasNext() returns true if a next element exists in the traversal.

- int next() advances the cursor and returns the next smallest value.

The first call to next() returns the smallest element in the BST.

You may assume that next() calls will always be valid.

Example 1:

Input

["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]

[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]

Output

[null, 3, 7, true, 9, true, 15, true, 20, false]

Example 2:

Explanation

BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);

bSTIterator.next(); // return 3

bSTIterator.next(); // return 7

bSTIterator.hasNext(); // return True

bSTIterator.next(); // return 9

bSTIterator.hasNext(); // return True

bSTIterator.next(); // return 15

bSTIterator.hasNext(); // return True

bSTIterator.next(); // return 20

bSTIterator.hasNext(); // return False

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        

    def next(self) -> int:
        

    def hasNext(self) -> bool:
        


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        

    def next(self) -> int:
        

    def hasNext(self) -> bool:
        


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()