LeetCode 105: Construct Binary Tree From Preorder And Inorder Traversal — Step-by-Step Visual Trace

#leetcode #python #algorithms #datastructures

Medium — Binary Tree | Recursion | Array | Tree Construction

The Problem

Given two arrays representing preorder and inorder traversals of a binary tree, reconstruct and return the original binary tree.

Approach

Use the preorder array to identify root nodes and the inorder array to determine left and right subtrees. Recursively build the tree by splitting the inorder array at each root's position and processing the corresponding preorder elements.

Time: O(n²) · Space: O(n)

Code

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:
            return None

        root_val = preorder.pop(0)
        root = TreeNode(root_val)
        root_index = inorder.index(root_val)

        root.left = self.buildTree(preorder, inorder[:root_index])
        root.right = self.buildTree(preorder, inorder[root_index + 1 :])

        return root