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: