We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Search Tree Iterator

Difficulty: Medium

Problem Description

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST). The class should provide methods to initialize the iterator, check if there are more elements to iterate, and retrieve the next element in the traversal.

Key Insights

  • The in-order traversal of a BST visits nodes in ascending order.
  • We can use a stack to keep track of the nodes as we traverse the tree.
  • The next() method should efficiently return the next smallest element, while hasNext() checks if there are more elements available.

Space and Time Complexity

Time Complexity:

  • hasNext(): O(1)
  • next(): O(1) on average Space Complexity: O(h), where h is the height of the tree, for storing the stack of nodes.

Solution

To solve the problem, we will implement the BSTIterator class using a stack to facilitate in-order traversal. The constructor will push all left children of the root onto the stack. The next() function will pop the top of the stack and push its right child (if it exists) and all its left children onto the stack. The hasNext() function simply checks if the stack is non-empty.

Code Solutions

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):
        self.stack = []
        self._push_left(root)

    def _push_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left

    def next(self) -> int:
        # The next smallest element is on the top of the stack
        node = self.stack.pop()
        # Push all the left children of the right subtree
        self._push_left(node.right)
        return node.val

    def hasNext(self) -> bool:
        return len(self.stack) > 0
← Back to All Questions