Python solution with detailed explanation

  • 0


    Binary Search Tree Iterator


    • Use a stack and initialize the stack with a walk along the left-most border.
    • next will pop the top of the stack. If the top has a right child, it will push all nodes along the left border of the subtree rooted at the right child.
    class BSTIterator(object):
        def __init__(self, root):
            :type root: TreeNode
   = []
            while root:
                root = root.left
        def hasNext(self):
            :rtype: bool
            return len( > 0
        def next(self):
            :rtype: int
            x =
            y = x.right
            while y:
                y = y.left
            return x.val

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.