Construct Binary Tree from Preorder and Inorder Traversal

Binary Tree
Medium

Approach

Diagrams

Analysis

Time

O(n)

Space

O(n)
class Solution:
    def buildTree(self, preorder, inorder):
        return self.dfs(preorder, inorder)

    def dfs(self, preorder, inorder):
        if not (inorder and preorder):
            return

        rootVal = preorder.pop(0)
        rootIdx = inorder.index(rootVal)
        root = TreeNode(rootVal)

        leftInorder = inorder[:rootIdx]
        rightInorder = inorder[rootIdx + 1:]

        leftPreorder = preorder[:len(leftInorder)]
        rightPreorder = preorder[len(leftPreorder):]

        root.left = self.dfs(leftPreorder, leftInorder)
        root.right = self.dfs(rightPreorder, rightInorder)

        return root

Learn

#Depth-First Search

Videos