CODEWITHSUNDEEP
pythonrecursiontreebinary-tree
Victor Cui
Victor Cui

Reputation: 1705

Construct Binary tree from Preorder and inorder Optimized solution not working

For Leetcode 105 I've got the O(N^2) solution working and I'm attempting to optimize to an O(N) solution but the output tree is the wrong structure.

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

My original O(N^2) solution.

def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        preorder_queue = deque(preorder)
        def helper(preorder, inorder):
            if not preorder or not inorder:
                return None
            root = TreeNode(preorder.popleft())
            root_index = inorder.index(root.val)
            root.left = helper(preorder, inorder[:root_index])
            root.right = helper(preorder, inorder[root_index+1:])
            return root
        return helper(preorder_queue, inorder)

The slow operation is here is the inorder.index(root.val) since an index operation in a list is O(N). I'm trying to optimize this by storing a map of Node values -> indexes in my solution below.

def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        preorder_queue = deque(preorder)
        cache = {}
        for i, node_val in enumerate(inorder):
            cache[node_val] = i
        def helper(preorder, inorder):
            if not preorder or not inorder:
                return None
            root = TreeNode(preorder.popleft())
            root_index = cache[root.val]
            root.left = helper(preorder, inorder[:root_index])
            root.right = helper(preorder, inorder[root_index+1:])
            return root
        return helper(preorder_queue, inorder)

However for the input preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7] my output is giving me [3,9,20,null,null,15,null,7] instead of the correct tree structure [3,9,20,null,null,15,7]. Can anyone explain what's wrong with the cache solution?

Upvotes: 1

Views: 118

Answers (1)

trincot
trincot

Reputation: 350137

The reason for the different output is this:

In the first version the value of root_index is taken from the local name inorder, which in general is just a slice of the original inorder (see how the recursive call is made with such a slice as argument). So the value of root_index is an index that is meaningful to the slice, but not to the overall, initial inorder list. Yet the second version of the code will give root_index an index that is meaningful in the initial inorder list, not to the local slice of it.

You can fix that by not creating a local inorder name (as parameter), but instead pass start and end indices which define which slice should be assumed, without actually creating it. That way the code can continue with the initial inorder list and use the indexing that the cache offers.

So:

    def helper(preorder, start, end):
        if not preorder or start >= end:
            return None
        root = TreeNode(preorder.popleft())
        root_index = cache[root.val]
        root.left = helper(preorder, start, root_index)
        root.right = helper(preorder, root_index+1, end)
        return root
    return helper(preorder_queue, 0, len(inorder))

Upvotes: 1

Related Questions