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 II

Number: 1729

Difficulty: Medium

Paid? Yes

Companies: Meta

Problem Description

Implement the BSTIterator class that supports bidirectional iteration over the in-order traversal of a binary search tree (BST). The iterator is initialized with a pointer set before the smallest element, and provides next() and prev() methods to move right and left, respectively, in the sorted order of the BST nodes.

Key Insights

  • In-order traversal of a BST produces a sorted sequence of elements.
  • Storing the in-order values in a list allows O(1) time for both next() and prev() accesses.
  • By initializing the pointer before the first element, the first call to next() will return the smallest element.
  • The approach efficiently handles the given constraints by precomputing the traversal.

Space and Time Complexity

Time Complexity: O(n) for the initial in-order traversal; O(1) for each next() and prev() call.
Space Complexity: O(n) for storing the in-order list of node values.

Solution

The solution involves performing an in-order traversal of the given BST during initialization to store all node values in a sorted list. A pointer (index) is then used to navigate through the list. The pointer starts at -1 to represent a position before the first element. Each call to next() increments the pointer and returns the associated value, while each call to prev() decrements it.
An alternative follow-up approach could avoid precomputing by using a stack to maintain the traversal state on-the-fly, but for simplicity and efficiency, the precomputed list is used.

Code Solutions

# 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):
        # Initialize the iterator by precomputing the in-order traversal.
        self.inorder = []
        self.index = -1  # Pointer is initialized before the first element.
        self._inorder_traversal(root)
    
    def _inorder_traversal(self, node):
        # Recursive in-order traversal (left, node, right).
        if not node:
            return
        self._inorder_traversal(node.left)
        self.inorder.append(node.val)
        self._inorder_traversal(node.right)
    
    def hasNext(self):
        # Returns true if there's an element right to the pointer.
        return self.index + 1 < len(self.inorder)
    
    def next(self):
        # Move the pointer right and return the element.
        self.index += 1
        return self.inorder[self.index]
    
    def hasPrev(self):
        # Returns true if there's an element left to the pointer.
        return self.index > 0
    
    def prev(self):
        # Move the pointer left and return the element.
        self.index -= 1
        return self.inorder[self.index]
← Back to All Questions