Python solution with detailed explanation


  • 0
    G

    Solution

    Binary Search Tree Iterator https://leetcode.com/problems/binary-search-tree-iterator/

    Algorithm

    • 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
            """
            self.st = []
            while root:
                self.st.append(root)
                root = root.left
            return
            
    
        def hasNext(self):
            """
            :rtype: bool
            """
            return len(self.st) > 0
            
    
        def next(self):
            """
            :rtype: int
            """
            x = self.st.pop()
            y = x.right
            while y:
                self.st.append(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.