Construct Binary Tree From Preorder And Inorder Traversal

LeetCode

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.

Initial attempt

Time spent: 1h 20m | Runtime: 79.86% | Memory: 96.19%

• I entered the problem not remembering what "inorder" and "preorder" were. This meant figuring it out based on the example, which took some time.
• The submission for the initial attempt was not exactly my own. I looked it up and found it. This was more of a failure than it looks like. My problem was that I overthought it.

Intuition

• The (obvious?) prerequisite here is knowing that inorder is {left,center,right} and preorder is {center,left,right}.
• After that, the recursion can be pretty straightforward as long as we're willing to be wasteful about array slicing.

Solution

• Build the tree recursively from top to bottom.
• This involves passing in the correct inorder/preorders down.
• An obvious point worth noting is that a subtree is the same size whether it's in inorder or preorder.

Cleaned up code

Time spent: 15m | Runtime: 11.70% | Memory: 11.04%

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder, inorder):
        return self.buildSubTree(preorder, inorder)

    def buildSubTree(self, preorder, inorder):
        if not preorder:
            return None

        # preorder: center, left, right
        # inorder: left, center, right

        center = preorder[0]

        # Everything up to the center.
        left_side_inorder = inorder[:inorder.index(center)]

        # Skip the first element (center), take the now-known size of
        # the left side.
        left_side_preorder = preorder[1:1 + len(left_side_inorder)]

        # Take everything after the left and center.
        right_side_inorder = inorder[inorder.index(center) + 1:]

        # Same idea as inorder - take everything after left and center.
        right_side_preorder = preorder[1 + len(left_side_inorder):]

        return TreeNode(
            val=center,
            left=self.buildSubTree(left_side_preorder, left_side_inorder),
            right=self.buildSubTree(right_side_preorder, right_side_inorder),
        )