173. Binary Search Tree Iterator

https://leetcode.com/problems/binary-search-tree-iterator/

Approach

In order traversal: Left -> Root -> Right

class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.stack = []
        self.pushLeft(root)

    def pushLeft(self, root):
        while root:
            self.stack.append(root)
            root = root.left

    # Moves the pointer to the right
    def next(self) -> int:
        node = self.stack.pop()
        # Move the pointer to right
        self.pushLeft(node.right)
        return node.val

    def hasNext(self) -> bool:
        return len(self.stack) > 0

Time Complexity:
Space Complexity:

sophryu99 / algorithm

173. Binary Search Tree Iterator #34

Approach