Build Binary Tree from Preorder and Inorder Traversal

Try to solve the Build Binary Tree from Preorder and Inorder Traversal problem.

We'll cover the following

Statement#

Create a binary tree from two integer arrays, p_order and i_order, where p_order represents a preorder traversal of a binary tree, and i_order represents an inorder traversal of the same tree.

Constraints:

  • 1≤1 \leq p_order.length, i_order.length ≤1000\leq1000
  • i_order.length ==== p_order.length
  • −1000≤-1000 \leq p_order[i], i_order[i] ≤1000\leq 1000
  • p_order and i_order consist of unique values.
  • Each value of i_order also appears in p_order and vice versa.

Examples#

Created with Fabric.js 3.6.6 Input Output Preorder Inorder 3 9 20 15 7 9 3 15 20 7 3 9 20 15 7 Sample example 1 ------------------------------------------------------------

1 of 2

Created with Fabric.js 3.6.6 Input Output Preorder Inorder 10 20 40 50 30 60 40 20 50 10 60 30 10 20 30 40 50 60 Sample example 2 ------------------------------------------------------------

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps us to check if you’re solving the correct problem:

Build Binary Tree from Preorder and Inorder Traversal

1

Select the correct binary tree constructed from preorder and inorder traversal:

preorder = [1, 12, 15, 6, 9, 5, 2]

inorder = [15, 12, 6, 1, 5, 9, 2]

A)
    1   /  \  12   9 / \  / \15  6 5  2 
B)
    12   /  \  1    9 / \  / \15  6 5  2 
C)
    15   /  \  12   9 / \  / \1  6 5   2 
D)
    9   /  \  1   12 / \  / \15  6 5  2 
Question 1 of 20 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Select the first element from the preorder list. Increment a preorder index variable to prepare for the next recursive call.

Create a new tree node with the selected element of the preorder list as its data.

Find the index of the selected element in the inorder list and store it in in_index.

Recursively build the left subtree of the root by calling the function on the elements before in_index in the inorder list.

Recursively build the right subtree of the root by calling the function on the elements after in_index in the inorder list.

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Input #1
Input #2
%0 node_01 3 node_11 9 node_21 20 node_31 15 node_41 7
Visualization for Input #1
Build Binary Tree from Preorder and Inorder Traversal

Solution: Binary Tree Right Side View

Solution: Build Binary Tree from Preorder and Inorder Traversal