Design Gurus Logo
Blind 75
Construct Binary Tree from Preorder and Inorder Traversal (medium)

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]
Image
  • 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]
Image
  • 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]
Image
  • 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