deepSWE.io

Construct Binary Tree from Preorder and Inorder Traversal

TreeDFSRecursion

20 min

Problem Statement

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.

Example

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output: [3,9,20,null,null,15,7]

Constraints

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
-3000 ≤ preorder[i], inorder[i] ≤ 3000
preorder and inorder consist of unique values.
Each value of inorder also appears in preorder.
preorder is guaranteed to be the preorder traversal of the tree.
inorder is guaranteed to be the inorder traversal of the tree.

Solution (DFS)

The solution uses a recursive Depth-First Search (DFS) approach to construct the tree. The key idea is to use the preorder traversal to find the root of a subtree and the inorder traversal to find the elements in the left and right subtrees.

Algorithm Steps

The first element of the preorder traversal is the root of the tree.
Find the root in the inorder traversal. The elements to the left of the root in the inorder traversal are in the left subtree, and the elements to the right are in the right subtree.
Recursively call the function to build the left and right subtrees.
To optimize finding the root in the inorder traversal, we can use a hash map to store the indices of the elements.

Construct Binary Tree from Preorder and Inorder Traversal Solution


# 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: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not inorder:
            return None
            
        root = TreeNode(preorder[0])
        mid = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:mid+1], inorder[:mid])
        root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])
        
        return root