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

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

Watch It Run

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

Comments