Construct binary tree from preorder and inorder traversal: wrong tree

The problem in your attempt is that the dictionary you have created provides indices in the original inorder list, while during recursion you provide slices of that list -- like inorder[root_index + 1:]. By consequence those indices found in the dictionary will not always be applicable to the slice you're working with.

To solve this particular issue, you could pass the start/stop indices as arguments instead of the slice itself. That way you keep the access to the original inorder list (so the index into it is correct) and can still see whether that virtual slice is empty, by comparing those start/stop indices.

Not a problem, but the base-case if condition can be simplified to only check the first condition. If ever the second condition is true (not preorder), the first one will be true as well, so in that case the second operand would not even be evaluated.

Secondly, you don't really need to perform that check before making the first recursive call. So you can just drop that very first if, unless you really want to have a fast solution for an empty input at the cost of executing that condition an extra time for all other inputs.

With that fix your code looks like this:

class Solution(object):
    def buildTree(self, preorder, inorder):
        inorder_map = {value: index for index, value in enumerate(inorder)}
        
        def buildSubTree(preorder, start, stop):  # pass start/stop instead of slice
            if start >= stop:  # enough as condition
                return None

            root_value = preorder.pop(0)
            root = TreeNode(root_value)

            root_index = inorder_map[root_value]  # Now this works

            root.left = buildSubTree(preorder, start, root_index)
            root.right = buildSubTree(preorder, root_index + 1, stop)
            
            return root
        
        return buildSubTree(preorder, 0, len(inorder))       

Still O(𝑛²)

Although performing an .index() call gave the original code a quadratic time complexity, there were also two other mechanisms that did that:

• taking slices of inorder: leads to quadratic complexity
• popping from the start of preorder: leads to quadratic complexity

The first of these two is already taken away with the fix above. For the second point we could create an iterator over preorder so that we can read values from that list in their order without actually removing them.

This gives us this O(𝑛) solution:

class Solution(object):
    def buildTree(self, preorder, inorder):
        inorder_map = {value: index for index, value in enumerate(inorder)}
        iterator = iter(preorder)  # no more need to do pop(0)
        
        def buildSubTree(start, stop):
            if start >= stop:
                return None

            root_value = iterator.next()  # preorder sequence
            root = TreeNode(root_value)

            root_index = inorder_map[root_value]

            root.left = buildSubTree(start, root_index)
            root.right = buildSubTree(root_index + 1, stop)
            
            return root
        
        return buildSubTree(0, len(inorder))

• Your second solution is still O(N ^ 2), because pop(0) itself is O(N).

• You can use deque() and popleft(), instead of pop(0):

• Here is the modified version:

from collections import deque


class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def buildTree(self, preorder, inorder):
        preorder = deque(preorder)
        inorder_map = {value: index for index, value in enumerate(inorder)}
        return self._buildTree(preorder, inorder_map, 0, len(inorder) - 1)

    def _buildTree(self, preorder, inorder_map, start, end):
        if start > end:
            return None

        root_value = preorder.popleft()
        root = TreeNode(root_value)
        root_index = inorder_map[root_value]

        root.left = self._buildTree(preorder, inorder_map, start, root_index - 1)
        root.right = self._buildTree(preorder, inorder_map, root_index + 1, end)

        return root


def test_buildTree():
    solution = Solution()

    preorder = [3, 9, 20, 15, 7]
    inorder = [9, 3, 15, 20, 7]
    root = solution.buildTree(preorder, inorder)

    assert root.val == 3
    assert root.left.val == 9
    assert root.right.val == 20
    assert root.right.left.val == 15
    assert root.right.right.val == 7

    print("Test passed.")


test_buildTree()

Prints

Test passed.