Construct Binary Tree from Preorder and Inorder Traversal (medium)
Go Back

## Problem Statement

Given the preorder and inorder traversal sequences of a binary tree, your task is to reconstruct this binary tree. Assume that the tree does not contain duplicate values.

### Example Generation

Example 1:

• Input:
• Preorder: [1,2,4,5,3,6,7]
• Inorder: [4,2,5,1,6,3,7]
• Expected Output:
• Tree Representation: [1,2,3,4,5,6,7]
• Justification:
• The first value in preorder (1) is the root. In the inorder list, everything left of value 1 is the left subtree and everything on the right is the right subtree. Following this pattern recursively helps in reconstructing the binary tree. All `null` value represents the leaf node.

Example 2:

• Input:
• Preorder: [8,5,9,7,1,12,2,4,11,3]
• Inorder: [9,5,1,7,2,12,8,4,3,11]
• Expected Output:
• Tree Representation: [8,5,4,9,7,11,1,12,2,null,3]
• Justification:
• Start with 8 (from preorder) as the root. Splitting at 8 in inorder, we find the left and right subtrees. Following this pattern recursively, we can construct the tree.

Example 3:

• Input:
• Preorder: [3,5,6,2,7,4,1,9,8]
• Inorder: [6,5,7,2,4,3,9,1,8]
• Expected Output:
• Tree Representation: [3,5,1,6,2,9,8,null,null,7,4]
• Justification:
• Following the same approach, using 3 as root from preorder, we split the inorder sequence into left and right subtrees and continue recursively.

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.

## Try it yourself

Try solving this question here:

Python3
Python3