Binary Search Tree Iterator - Leetcode Solution

The Binary Search Tree Iterator problem on LeetCode is an interesting challenge that requires a good understanding of Binary Search Trees and Iterators. The problem requires us to implement an Iterator for a Binary Search Tree. The Iterator should be able to iterate through all the elements in the Binary Search Tree in ascending order.

Here is the detailed solution for the Binary Search Tree Iterator problem on LeetCode:

Step 1: Implement the Binary Search Tree

Before we can create an Iterator for a Binary Search Tree, we need to implement the Binary Search Tree itself. The Binary Search Tree is a tree structure that is made up of nodes. Each node contains a value and two pointers to other nodes, namely the left child and the right child.

Here is the implementation of the Binary Search Tree in Python:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        if self.root is None:
            self.root = TreeNode(val)
            return

        node = self.root
        while True:
            if val < node.val:
                if node.left is None:
                    node.left = TreeNode(val)
                    return
                node = node.left
            else:
                if node.right is None:
                    node.right = TreeNode(val)
                    return
                node = node.right

    def inorder_traversal(self, node, values):
        if node:
            self.inorder_traversal(node.left, values)
            values.append(node.val)
            self.inorder_traversal(node.right, values)

    def inorder_values(self):
        values = []
        self.inorder_traversal(self.root, values)
        return values

The above implementation defines a TreeNode class that represents the nodes in the Binary Search Tree. It also defines the BST class that represents the Binary Search Tree itself. The BST class has a root attribute that holds the root of the Binary Search Tree.

The BST class also has an insert method that inserts a new value into the Binary Search Tree. This method traverses the Binary Search Tree from the root, searching for the appropriate position to insert the new value.

The inorder_traversal method is used to traverse the Binary Search Tree in the inorder manner. It takes a node and an empty list as arguments, and it recursively traverses the left subtree, appends the value of the current node to the list, and then recursively traverses the right subtree.

Finally, the inorder_values method calls the inorder_traversal method with the root of the Binary Search Tree and an empty list. It returns the values in the list in sorted order.

Step 2: Implement the Iterator

Now that we have implemented the Binary Search Tree, we can create an Iterator to traverse the Binary Search Tree in ascending order.

Here is an implementation of the Iterator in Python:

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self.current = root

    def has_next(self):
        return self.current is not None or len(self.stack) > 0

    def next(self):
        while self.current:
            self.stack.append(self.current)
            self.current = self.current.left

        self.current = self.stack.pop()
        val = self.current.val
        self.current = self.current.right
        return val

The above implementation defines a BSTIterator class that takes the root of the Binary Search Tree as its argument. The BSTIterator class has two methods: has_next and next.

The has_next method returns a boolean value that indicates whether there are more elements in the Binary Search Tree to iterate through. It does this by checking whether the current value is None or whether there are more elements in the stack.

The next method returns the next element in the Binary Search Tree. It does this by first traversing the left subtree of the current node and pushing all the nodes onto the stack. It then pops the top element from the stack, sets the current node to its right child, and returns the value of the popped element.

The Iterator uses a stack to keep track of the elements that have been visited but not yet returned. The Iterator first pushes all the nodes in the left subtree of the current node onto the stack. It then pops the top element from the stack, sets the current node to its right child, and returns the value of the popped element.

Step 3: Testing

To test the Iterator, we can create a Binary Search Tree and insert some random values. We can then create an instance of the BSTIterator class and iterate through the Binary Search Tree using the next method.

Here is an example of how to test the Iterator:

bst = BST()
bst.insert(7)
bst.insert(3)
bst.insert(15)
bst.insert(9)
bst.insert(20)

iterator = BSTIterator(bst.root)

while iterator.has_next():
    print(iterator.next())

The above code creates a Binary Search Tree with the values 7, 3, 15, 9, and 20. It then creates an instance of the BSTIterator class with the root of the Binary Search Tree and iterates through the Binary Search Tree using the next method. The output of the above code would be:

3
7
9
15
20

This is because the BSTIterator iterates through the Binary Search Tree in ascending order, starting with the smallest value (3) and ending with the largest value (20).

That's it! The Binary Search Tree Iterator problem on LeetCode has been solved.

1