Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Build Binary Tree from Preorder and Inorder Traversal

Understand how to build a binary tree given its preorder and inorder traversal sequences. Learn to analyze traversal arrays, apply depth-first search concepts, and implement a solution that reconstructs the original tree structure, enhancing your skills in tree-based problems.

We'll cover the following...

Statement

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

Constraints:

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

Examples

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
1 / 2

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.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4
5

Try it yourself

Implement your solution in the following coding playground.

Java
usercode > Solution.java
import java.util.*;
import ds_v1.BinaryTree.TreeNode;
// Definiton of a binary tree node class
// class TreeNode<T> {
//     T data;
//     TreeNode<T> left;
//     TreeNode<T> right;
//     TreeNode(T data) {
//         this.data = data;
//         this.left = null;
//         this.right = null;
//     }
// }
public class Solution {
    
    public static TreeNode<Integer> buildTree(int[] pOrder, int[] iOrder) {
        // Replace this placeholder return statement with your code
        return new TreeNode<Integer>(-1);
    }
}
Build Binary Tree from Preorder and Inorder Traversal