Python, Very simple

  • -1

    Simply do the inorder traversal of the given BST and store it in a list and use a simple iterator on this list.

    # Definition for a  binary tree node
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class BSTIterator(object):
        def inOrder(self, root, lis):
            if root:
                self.inOrder(root.left, lis)
                self.inOrder(root.right, lis)
            return lis
        def __init__(self, root):
            :type root: TreeNode
            self.arr = []
            if root is not None:
                self.inOrder(root, self.arr)
            self.current = 0
        def hasNext(self):
            :rtype: bool
            return (self.current < len(self.arr))
        def next(self):
            :rtype: int
            if self.current < len(self.arr):
                ret = self.arr[self.current]
                self.current += 1        
                return ret
            return None
    # Your BSTIterator will be called like this:
    # i, v = BSTIterator(root), []
    # while i.hasNext(): v.append(

  • 0

    This is not oh(h) solution.

  • 0

    @vbhargava4 Exactly. The memory complexity is O(2^h) not O(h)

Log in to reply

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