Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Construct Binary Tree from Preorder and Inorder Traversal (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible