Build a Binary Tree From Preorder and Inorder Traversals

Reconstruct a binary tree given its preorder and inorder traversals. This tests understanding of tree traversals and recursive algorithms, crucial for many data structure-related interview questions.

treerecursionbinary-treedivide-and-conquerhash-map

Problem Statement

You are given two integer arrays, preorder and inorder, representing the preorder and inorder traversals of a binary tree, respectively. Your task is to reconstruct the binary tree from these traversals and return the root node of the reconstructed tree. Assume that the tree contains unique values.

Example 1

Input: {'preorder': [10, 5, 2, 8, 15, 12, 20], 'inorder': [2, 5, 8, 10, 12, 15, 20]}

Output: Binary tree with root 10, left subtree (5, 2, 8) and right subtree (15, 12, 20)

The preorder traversal tells us the root is 10. The inorder traversal tells us that 2, 5, and 8 are in the left subtree and 12, 15, and 20 are in the right subtree. Recursively apply this logic to construct the entire tree.

Example 2

Input: {'preorder': [1, 2, 3], 'inorder': [2, 1, 3]}

Output: Binary tree with root 1, left child 2, and right child 3

The preorder traversal starts with 1, which is the root. Inorder traversal shows 2 is to the left of 1 and 3 is to the right. This forms a simple tree structure.

Constraints

-1 <= preorder.length <= 3000
-inorder.length == preorder.length
--3000 <= preorder[i], inorder[i] <= 3000
-preorder and inorder consist of unique values
-inorder is guaranteed to be an inorder traversal of the tree

Brute Force Approach

A brute-force approach would involve iterating through all possible binary tree configurations and checking if their preorder and inorder traversals match the given arrays. Imagine trying to assemble a jigsaw puzzle by randomly placing pieces until they fit. This is extremely inefficient, as the number of possible tree configurations grows exponentially with the number of nodes.

TimeO(n!)

SpaceO(n)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem