Construct a tree from Inorder and Level order traversals | Set 1

Last Updated : 23 Jul, 2025

Given in-order and level-order traversals of a Binary Tree, the task is to construct the Binary Tree and return its root.

Example:

Input:
in[] = {4, 8, 10, 12, 14, 20, 22};
level[] = {20, 8, 22, 4, 12, 10, 14};
Output:

Approach:

The idea is to construct the root node from the first element of the level order array. Find the index of this element in the in-order array. Recursively create the left subtree from the elements present on the left side to the current element in the in-order array. Similarly, create the right subtree from the elements present on the right side to the current element in the in-order array.

Below is the implementation of the above approach:

C++

// c++ program to construct tree using  // inorder and levelorder traversals #include <bits/stdc++.h> using namespace std; class Node {  public:  int key;  Node *left, *right;  Node(int x) {  key = x;  left = nullptr;  right = nullptr;  } }; // Function to find the index of an element. int searchValue(vector<int> in, int value, int s, int e) {    for (int i=s; i<=e; i++) {  if (in[i] == value)  return i;  }  return -1; } // Recursive function to build the binary tree. Node* buildTreeRecur(vector<int> in,   vector<int> level, int s, int e) {    // For empty array, return null  if (s>e) {  return nullptr;  }    // create the root Node  Node* root = new Node(level[0]);    // find the index of first element of level array  // in the in-order array.  int index = searchValue(in, level[0], s, e);    int lCnt = index-s, rCnt = e - index;    // Level order array for left and right subtree.  vector<int> lLevel(lCnt);  vector<int> rLevel(rCnt);    // add the left and right elements to lLevel and   // rLevel  int l = 0, r = 0;  for (int i = 1; i< e-s+1; i++) {  int j = searchValue(in, level[i], s, e);    // If the value is present in  // left subtree.  if (j<index)  lLevel[l++] = level[i];    // else it will be present in   // right subtree.  else   rLevel[r++] = level[i];  }    // Recursively create the left and right subtree.  root->left = buildTreeRecur(in, lLevel, s, index-1);  root->right = buildTreeRecur(in, rLevel, index+1, e);    return root; } Node* buildTree(vector<int> inorder, vector<int> level, int n) {    // Build the tree recursively.  Node* root = buildTreeRecur(inorder, level, 0, n-1);    return root; } void printInorder(Node* head) {  Node* curr = head;  if (curr == nullptr)  return;  printInorder(curr->left);  cout << curr->key << " ";  printInorder(curr->right); } int main() {  vector<int> in = { 4, 8, 10, 12, 14, 20, 22 };  vector<int> level = { 20, 8, 22, 4, 12, 10, 14 };  int n = level.size();  Node* root = buildTree(in, level, n);  printInorder(root);  return 0; }

Java

// Java Program to construct tree using  // inorder and levelorder traversals import java.util.*; class Node {  int key;  Node left, right;  Node(int x) {  key = x;  left = null;  right = null;  } } class GfG {  // Function to find the index of an element.  static int searchValue(ArrayList<Integer> in, int value, int s, int e) {  for (int i = s; i <= e; i++) {  if (in.get(i) == value)  return i;  }  return -1;  }  // Recursive function to build the binary tree.  static Node buildTreeRecur(ArrayList<Integer> in,  ArrayList<Integer> level, int s, int e) {  // For empty array, return null  if (s > e) {  return null;  }  // create the root Node  Node root = new Node(level.get(0));  // find the index of first element of level array  // in the in-order array.  int index = searchValue(in, level.get(0), s, e);  int lCnt = index - s, rCnt = e - index;  // Level order array for left and right subtree.  ArrayList<Integer> lLevel = new ArrayList<>(lCnt);  ArrayList<Integer> rLevel = new ArrayList<>(rCnt);  // add the left and right elements to lLevel and rLevel  int l = 0, r = 0;  for (int i = 1; i < e - s + 1; i++) {  int j = searchValue(in, level.get(i), s, e);  // If the value is present in left subtree.  if (j < index)  lLevel.add(level.get(i));  // else it will be present in right subtree.  else  rLevel.add(level.get(i));  }  // Recursively create the left and right subtree.  root.left = buildTreeRecur(in, lLevel, s, index - 1);  root.right = buildTreeRecur(in, rLevel, index + 1, e);  return root;  }  static Node buildTree(ArrayList<Integer> inorder, ArrayList<Integer> level, int n) {  // Build the tree recursively.  return buildTreeRecur(inorder, level, 0, n - 1);  }  static void printInorder(Node head) {  if (head == null)  return;  printInorder(head.left);  System.out.print(head.key + " ");  printInorder(head.right);  }  public static void main(String[] args) {  ArrayList<Integer> in =   new ArrayList<>(Arrays.asList(4, 8, 10, 12, 14, 20, 22));  ArrayList<Integer> level =  new ArrayList<>(Arrays.asList(20, 8, 22, 4, 12, 10, 14));  int n = in.size();  Node root = buildTree(in, level, n);  printInorder(root);  } }

Python

# Python Program to construct tree using  # inorder and levelorder traversals class Node: def __init__(self, key): self.key = key self.left = None self.right = None # Function to find the index of an element. def searchValue(inorder, value, s, e): for i in range(s, e + 1): if inorder[i] == value: return i return -1 # Recursive function to build the binary tree. def buildTreeRecur(inorder, level, s, e): # For empty array, return None if s > e: return None # create the root Node root = Node(level[0]) # find the index of first element of level array # in the in-order array. index = searchValue(inorder, level[0], s, e) # Level order array for left and right subtree. lLevel = [] rLevel = [] # add the left and right elements to lLevel and rLevel for i in range(1, e - s + 1): j = searchValue(inorder, level[i], s, e) if j < index: lLevel.append(level[i]) else: rLevel.append(level[i]) # Recursively create the left and right subtree. root.left = buildTreeRecur(inorder, lLevel, s, index - 1) root.right = buildTreeRecur(inorder, rLevel, index + 1, e) return root def buildTree(inorder, level, n): return buildTreeRecur(inorder, level, 0, n - 1) def printInorder(head): if head is None: return printInorder(head.left) print(head.key, end=" ") printInorder(head.right) if __name__ == "__main__": inorder = [4, 8, 10, 12, 14, 20, 22] level = [20, 8, 22, 4, 12, 10, 14] n = len(inorder) root = buildTree(inorder, level, n) printInorder(root)

// C# Program to construct tree using  // inorder and levelorder traversals using System; using System.Collections.Generic; class Node {  public int key;  public Node left, right;  public Node(int x) {  key = x;  left = null;  right = null;  } } class GfG {    // Function to find the index of an element.  static int SearchValue(List<int> inorder,   int value, int s, int e) {  for (int i = s; i <= e; i++) {  if (inorder[i] == value)  return i;  }  return -1;  }  // Recursive function to build the binary tree.  static Node BuildTreeRecur(List<int> inorder,   List<int> level, int s, int e) {  // For empty array, return null  if (s > e) {  return null;  }  // create the root Node  Node root = new Node(level[0]);  // find the index of first element of level array  // in the in-order array.  int index = SearchValue(inorder, level[0], s, e);  int lCnt = index - s, rCnt = e - index;  // Level order array for left and right subtree.  List<int> lLevel = new List<int>(lCnt);  List<int> rLevel = new List<int>(rCnt);  // add the left and right elements to lLevel and rLevel  for (int i = 1; i < e - s + 1; i++) {  int j = SearchValue(inorder, level[i], s, e);  // If the value is present in left subtree.  if (j < index)  lLevel.Add(level[i]);  else  rLevel.Add(level[i]);  }  // Recursively create the left and right subtree.  root.left = BuildTreeRecur(inorder, lLevel, s, index - 1);  root.right = BuildTreeRecur(inorder, rLevel, index + 1, e);  return root;  }  static Node BuildTree(List<int> inorder, List<int> level, int n) {  return BuildTreeRecur(inorder, level, 0, n - 1);  }  static void PrintInorder(Node head) {  if (head == null)  return;  PrintInorder(head.left);  Console.Write(head.key + " ");  PrintInorder(head.right);  }  static void Main(string[] args) {  List<int> inorder = new List<int> { 4, 8, 10, 12, 14, 20, 22 };  List<int> level = new List<int> { 20, 8, 22, 4, 12, 10, 14 };  int n = inorder.Count;  Node root = BuildTree(inorder, level, n);  PrintInorder(root);  } }

JavaScript

// JavaScript Program to construct tree using  // inorder and levelorder traversals class Node {  constructor(key) {  this.key = key;  this.left = null;  this.right = null;  } } // Function to find the index of an element. function searchValue(inorder, value, s, e) {  for (let i = s; i <= e; i++) {  if (inorder[i] === value) {  return i;  }  }  return -1; } // Recursive function to build the binary tree. function buildTreeRecur(inorder, level, s, e) {    // For empty array, return null  if (s > e) {  return null;  }  // create the root Node  const root = new Node(level[0]);    // find the index of first element of level array  // in the in-order array.  const index = searchValue(inorder, level[0], s, e);  // Level order array for left and right subtree.  const lLevel = [];  const rLevel = [];  // add the left and right elements to lLevel and   // rLevel  let l = 0, r = 0;  for (let i = 1; i < e - s + 1; i++) {  const j = searchValue(inorder, level[i], s, e);    // If the value is present in  // left subtree.   if (j < index) {  lLevel[l++] = level[i];  }    // else it will be present in   // right subtree.  else {  rLevel[r++] = level[i];  }  }  // Recursively create the left and right subtree.  root.left = buildTreeRecur(inorder, lLevel, s, index - 1);  root.right = buildTreeRecur(inorder, rLevel, index + 1, e);  return root; } function buildTree(inorder, level, n) {  return buildTreeRecur(inorder, level, 0, n - 1); } function printInorder(head) {  if (!head) {  return;  }  printInorder(head.left);  console.log(head.key);  printInorder(head.right); } const inorder = [4, 8, 10, 12, 14, 20, 22]; const level = [20, 8, 22, 4, 12, 10, 14]; const n = inorder.length; const root = buildTree(inorder, level, n); printInorder(root);