#173

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Binary Search Tree Iterator

Implement an iterator for in-order traversal of a binary search tree (BST), maintaining traversal state with stack-based operations.

stack tree design binary search tree binary tree

Problem Statement

The task is to implement the BSTIterator class that represents an iterator for the in-order traversal of a binary search tree (BST). The iterator should maintain its state and return elements in ascending order. You will be given the root of the BST, and your solution should efficiently track the current position while supporting next() and hasNext() calls.

The next() method should return the next smallest number in the in-order traversal of the tree, while hasNext() should return whether there are any more elements to traverse. The challenge involves designing the iterator with minimal space and time complexity by leveraging the stack for efficient traversal. Additionally, assume that calls to next() will always return a valid number.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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]

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

Constraints

The number of nodes in the tree is in the range [1, 105].
0 <= Node.val <= 106
At most 105 calls will be made to hasNext, and next.

Solution Approach

In-order Traversal Using a Stack

The core approach for this problem is to use a stack to store nodes while performing an in-order traversal. The stack will help maintain the traversal state by storing nodes as we descend into the left subtree. By popping nodes from the stack, we can easily access the next smallest node in the traversal. Each call to next() will pop a node from the stack, ensuring the elements are returned in ascending order.

Efficient State Management

Efficiently managing the traversal state is key to this solution. By using the stack, we can traverse down the left subtree to reach the smallest element, and only store the necessary nodes in the stack to ensure constant time for next() and hasNext(). This minimizes both time and space complexities.

Optimization Considerations

To optimize performance, we can avoid recomputing the traversal state by ensuring the stack always contains the necessary nodes as we move through the tree. Space and time complexity should be minimized by controlling the size of the stack and ensuring that next() and hasNext() calls are handled in constant time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of each operation is O(1) because the next() and hasNext() methods depend on stack operations, which are constant time. The space complexity is O(h), where h is the height of the tree, due to the stack storing nodes along the traversal path.

What Interviewers Usually Probe

The candidate demonstrates familiarity with in-order traversal techniques and stack manipulation for maintaining state during iteration.
The candidate designs an efficient iterator that avoids unnecessary traversal steps and optimizes memory usage for large trees.
The candidate clearly explains the trade-off between space and time complexity in relation to the stack-based approach.

Common Pitfalls or Variants

Common pitfalls

Failing to properly manage the stack state, resulting in incorrect traversal order or invalid next() calls.
Overcomplicating the solution by trying to maintain a full in-memory list of the tree elements, leading to higher space complexity.
Not handling edge cases like empty trees or one-node trees effectively.

Follow-up variants

Implementing the iterator for a different type of traversal, such as pre-order or post-order.
Optimizing the iterator design for a tree with an unbalanced structure, where depth could vary greatly.
Implementing a version of the iterator that supports reverse traversal of the BST.

FAQ

What is the primary pattern for solving the Binary Search Tree Iterator problem?

The primary pattern for this problem is binary-tree traversal with state tracking, specifically using a stack to manage the traversal state and return elements in order.

How do I ensure efficient space and time complexity in the BSTIterator?

Efficient space and time complexity are achieved by using a stack to manage the traversal state and minimizing the space used for tree nodes, ensuring that each next() and hasNext() call operates in constant time.

What is the time complexity for each operation in the Binary Search Tree Iterator?

Each operation (next() and hasNext()) has a time complexity of O(1) due to the constant time stack operations used to traverse and manage the tree.

What edge cases should I consider when implementing the BSTIterator?

Edge cases to consider include empty trees, one-node trees, and trees with a highly unbalanced structure. Ensure that next() and hasNext() handle these situations correctly.

How can I optimize the Binary Search Tree Iterator for a tree with a large number of nodes?

To optimize the iterator for large trees, focus on minimizing the stack size by only storing necessary nodes and avoiding unnecessary recomputations during traversal.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

# 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: TreeNode):
        def inorder(root):
            if root:
                inorder(root.left)
                self.vals.append(root.val)
                inorder(root.right)

        self.cur = 0
        self.vals = []
        inorder(root)

    def next(self) -> int:
        res = self.vals[self.cur]
        self.cur += 1
        return res

    def hasNext(self) -> bool:
        return self.cur < len(self.vals)


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

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

# 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: TreeNode):
        def inorder(root):
            if root:
                inorder(root.left)
                self.vals.append(root.val)
                inorder(root.right)

        self.cur = 0
        self.vals = []
        inorder(root)

    def next(self) -> int:
        res = self.vals[self.cur]
        self.cur += 1
        return res

    def hasNext(self) -> bool:
        return self.cur < len(self.vals)


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

Continue Practicing

#341 flatten nested list iterator #449 serialize and deserialize bst #703 kth largest element in a stream