Construct a tree from Inorder and Level order traversals

You are given inorder and level order traversals. Create a Binary Tree using these given traversals.

Inorder: In this traversal, we first visit the left subtree, then the root node, and the right subtree at the end.

Level order: In this traversal, we visit every node on a level before approaching the next level, in the top to bottom fashion. This traversal is also known as the breadth-first traversal of the tree.

Example 1:

Input: preorder = [4, 8, 10, 12, 14, 20, 22], 
inorder = [20,8,22,4,12,10,14]
Output:  [20,8,22,4,12,10,14]

Explanation:

As we already know that the first element of the level-order array is the root node. Therefore, 20 will be the root of the tree. Then, we can get the elements of the left subtree by simply searching 20 in the inorder array as the elements of the left subtree reside before the root node in the inorder array. Similarly, elements on the right side of 20 in the inorder array would be the elements of the right subtree. Hence, we get the output: [3,9,20,null,null,15,7]

Approach 1

The idea is that, as we know, the first element of the level order array is the root node. Then, we can get the elements of the left subtree by simply searching the root element in the inorder array, as the elements of the left subtree reside before the root node in the inorder array. Similarly, elements on the right side of the root element in the inorder array would be the elements of the right subtree.

Algorithm

1. Define the function findIndex, which searches the index of the given value, passed as the parameter.
2. Extract keys that are present in the left subtree and right subtree of the inorder array from the level order array.
3. Create a node with the value being set as the data that is passed as the parameter and initializing its left and right children to NULL.
4. Build a binary tree from the given 2 arrays of integers, inorder & level order.
5. Return null if the ending index is less than the starting index.
6. Else, take root from the level order array, as its first node is the root.
7. Return root if the tree has no children.
8. Otherwise, look for the root's index in the inorder array.
9. After getting the index of the root, extract the nodes of the left subtree from the level order array.
10. Similarly, after getting the index of the root, extract the nodes of the right subtree from the level order array.
11. Build the left and the right subtrees from the extracted nodes.

The implementation of the above-discussed approach is:

C++ Programming

#include <bits/stdc++.h>
using namespace std;

// Structure for a node
// having an integer value, data
// and two pointers
// to store the references of the
// left and right children
struct Node {
	int key;
	struct Node *left, *right;
};

// defining the function findIndex,
// that searches the index of the given 
// value, passed as the parameter.
int findIndex(int arr[], int strt, int end, int value)
{
	for (int i = strt; i <= end; i++)
		if (arr[i] == value)
			return i;
	return -1;
}

// function to extract keys that are present in the
// left subtree and right subtree
// of the inorder array,
// from the level order array.
int* extractNodes(int in[], int level[], int m, int n)
{
	int *newlevel = new int[m], j = 0;
	for (int i = 0; i < n; i++) if (findIndex(in, 0, m - 1, level[i]) != -1) newlevel[j] = level[i], j++; return newlevel; } // function to create a node // with the value being set as the data // that is passed as the parameter, // and initializing its left and right children to NULL Node* newNode(int key) { Node* node = new Node; node->key = key;
	node->left = node->right = NULL;
	return (node);
}

// function to build a binary tree
// from the given 2 arrays of integers, 
// inorder & level order.
Node* constructBinaryTree(int in[], int level[], int inStrt,
				int inEnd, int n)
{
	// return null if, ending index is less than the
	// starting index.
	if (inStrt > inEnd)
		return NULL;

	// take root from the level order array,
	// as its first node is the root.
	Node* root = newNode(level[0]);

	// return root, if the tree has no children.
	if (inStrt == inEnd)
		return root;

	// otherwise look for the
	// root's index in the inorder array
	int inIndex = findIndex(in, inStrt, inEnd, root->key);

	// after getting the index of root,
	// extract the nodes of the left subtree
	// from the level order array.
	int* llevel = extractNodes(in, level, inIndex, n);

	// similarly, after getting the index of root,
	// extract the nodes of the right subtree
	// from the level order array.
	int* rlevel
		= extractNodes(in + inIndex + 1, level, n - 1, n);

	// build the left and the right subtrees, 
	// from the extracted nodes.
	root->left = constructBinaryTree(in, llevel, inStrt, inIndex - 1,
						inIndex - inStrt);
	root->right = constructBinaryTree(in, rlevel, inIndex + 1, inEnd,
							inEnd - inIndex);

	// handling the memory leak situation
	delete[] llevel;
	delete[] rlevel;

	return root;
}

// function to print the 
// constructed tree.
void printTree(Node* node)
{
	if (node == NULL)
		return;
	printTree(node->left);
	cout << node->key << " "; printTree(node->right);
}

int main()
{
	int in[] = { 4, 8, 10, 12, 14, 20, 22 };
	int level[] = { 20, 8, 22, 4, 12, 10, 14 };
	int n = sizeof(in) / sizeof(in[0]);
	Node* root = constructBinaryTree(in, level, 0, n - 1, n);

	cout << "Constructed Tree is (Inorder Traversal):\n";
	printTree(root);
	cout<<endl;
	return 0;
}

Output

Constructed Tree is (Inorder Traversal):
4 8 10 12 14 20 22

Java Programming

// Class for a node
// having an integer value, data
// and two pointers
// to store the references of the
// left and right children
class Node {
    int data;
    Node left, right;

    Node(int item)
    {
        data = item;
        left = right = null;
    }

    public void setLeft(Node left) { this.left = left; }

    public void setRight(Node right) { this.right = right; }
}

class Tree {
    Node root;

    Node constructBinaryTree(int in[], int level[])
    {
        Node startnode = null;
        return constructTree(startnode, level, in, 0,
                            in.length - 1);
    }

    Node constructTree(Node startNode, int[] levelOrder,
                    int[] inOrder, int inStart,
                    int inEnd)
    {

        // return null if, ending index is less than the
        // starting index.
        if (inStart > inEnd)
            return null;

        if (inStart == inEnd)
            return new Node(inOrder[inStart]);

        boolean found = false;
        int index = 0;

        // search for the index of the first element of the
        // level order array,  
        // in the inorder array.
        for (int i = 0; i < levelOrder.length - 1; i++) {
            int data = levelOrder[i];
            for (int j = inStart; j < inEnd; j++) {
                if (data == inOrder[j]) {
                    startNode = new Node(data);
                    index = j;
                    found = true;
                    break;
                }
            }
            if (found == true)
                break;
        }

        // after getting the index of root,
        // extract the nodes of the left subtree
        // from the level order array.
        startNode.setLeft(
            constructTree(startNode, levelOrder, inOrder,
                        inStart, index - 1));
        
        // similarly, after getting the index of root,
        // extract the nodes of the left subtree
        // from the level order array.
        startNode.setRight(
            constructTree(startNode, levelOrder, inOrder,
                        index + 1, inEnd));

        return startNode;
    }

    // function to print the 
    // constructed tree.
    void printTree(Node node)
    {
        if (node == null)
            return;
        printTree(node.left);
        System.out.print(node.data + " ");
        printTree(node.right);
    }

    public static void main(String args[])
    {
        Tree tree = new Tree();
        int in[] = new int[] { 4, 8, 10, 12, 14, 20, 22 };
        int level[]
            = new int[] { 20, 8, 22, 4, 12, 10, 14 };
        int n = in.length;
        Node node = tree.constructBinaryTree(in, level);

        System.out.println("Constructed Tree is (Inorder Traversal):");
        tree.printTree(node);
        System.out.println();
    }
}

Output

Constructed Tree is (Inorder Traversal):
4 8 10 12 14 20 22

Python Programming

# Class for a node
# having an integer value, data
# and two pointers
# to store the references of the
# left and right children
class Node:

    def __init__(self, key):
        self.data = key
        self.left = None
        self.right = None


# function to build a binary tree
# from the given 2 arrays of integers,
# inorder & level order.
def constructBinaryTree(level, ino):

    if ino:

        # to check that if the given node
        # is presents in the level order array
        for i in range(0, len(level)):

            if level[i] in ino:

                # if the given node is found,
                # then create a new node assigning its value
                # as this node.
                node = Node(level[i])

                # find that node's index
                # in the level order array
                io_index = ino.index(level[i])
                break

        # return if the inorder is empty
        if not ino:
            return node

        # building the left subtree
        # and the right subtree
        node.left = constructBinaryTree(level, ino[0:io_index])
        node.right = constructBinaryTree(level, ino[io_index + 1:len(ino)])
        return node

# function to print the
# constructed tree.
def printTree(node):
    if node is None:
        return

    printTree(node.left)

    print(node.data, end=" ")

    printTree(node.right)

# Driver code

levelorder = [20, 8, 22, 4, 12, 10, 14]
inorder = [4, 8, 10, 12, 14, 20, 22]

ino_len = len(inorder)
root = constructBinaryTree(levelorder, inorder)

print("Constructed Tree is (Inorder Traversal):")
printTree(root)
print()

Output

Constructed Tree is (Inorder Traversal):
4 8 10 12 14 20 22

Complexity Analysis

Time Complexity : O(n^3) where n is the number of nodes of the Binary Tree.

Approach 2

This approach is better than the previous one as it solves this problem in O(n^2) time. Here, we are using a hash table to store the values of the root node and the elements belonging to the left subtree. Then we will search if the root node falls in the left subtree or not.

Algorithm

1. Create a node with the value being set as the data that is passed as the parameter, and initializing its left and right children to NULL.
2. Build a binary tree from the given 2 arrays of integers, inorder & level order.
3. Search for the index of the first element of the level order array, in the inorder array.
4. Search for the index of the first element of the level order array in the inorder array, as it's the root of the tree.
5. Create the root node of the desired tree
6. Create the left subtree of the desired tree.
7. Create the right subtree of the desired tree.
8. Return root
9. Function to build a binary tree.
10. From the given 2 arrays of integers, inorder & level order.
11. Use map to search for the index of any node in the level order array.
12. Return the constructed tree.

The implementation of the above-discussed approach is:

C++ Programming

#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
using namespace std;
 
// Structure for a node
// having an integer value, data
// and two pointers
// to store the references of the
// left and right children
struct Node
{
    int data;
    Node* left, *right;
};
 
// function to create a node
// with the value being set as the data
// that is passed as the parameter,
// and initializing its left and right children to NULL
Node* newNode(int key)
{
    Node* node = new Node;
    node->data = key;
    node->left = node->right = nullptr;
 
    return node;
}
 
// function to print the 
// constructed tree.
void printTree(Node* root)
{
    if (root == nullptr) {
        return;
    }
 
    printTree(root->left);
    cout << root->data << " "; printTree(root->right);
}
 
// function to build a binary tree
// from the given 2 arrays of integers, 
// inorder & level order.
Node* constructBinaryTree(int inorder[], int start, int end,
                unordered_map<int, int> map)
{
    // base case
    if (start > end) {
        return nullptr;
    }
 
    // search for the index of the first element of the
	// level order array,  
	// in the inorder array.
    int index = start;
    for (int j = start + 1; j <= end; j++)
    {
        // search for the index of the first element of the
		// level order array,  
		// in the inorder array, as it's the root of the
		// tree.
        if (map[inorder[j]] < map[inorder[index]]) { index = j; } } // create the root node of the desired tree Node* root = newNode(inorder[index]); // create the left subtree of the desired tree. root->left = constructBinaryTree(inorder, start, index - 1, map);
 
    // create the right subtree of the desired tree.
    root->right = constructBinaryTree(inorder, index + 1, end, map);
 
    // return root 
    return root;
}
 
// function to build a binary tree
// from the given 2 arrays of integers, 
// inorder & level order.
Node* constructBinaryTree(int in[], int level[], int n)
{
	// map to search for the
	// index of any node in the level order array.
    unordered_map<int, int> map;
    for (int i = 0; i < n; i++) {
        map[level[i]] = i;
    }
 
	// finally, return the constructed tree.
    return constructBinaryTree(in, 0, n - 1, map);
}
 
int main()
{
    int inorder[] = { 4, 2, 5, 1, 6, 3, 7 };
    int level[]    = { 1, 2, 3, 4, 5, 6, 7 };
    int n = sizeof(inorder)/sizeof(inorder[0]);
 
    Node* root = constructBinaryTree(inorder, level, n);
 
    cout << "Constructed Tree is (Inorder Traversal):\n";
    printTree(root);
    cout<<endl;
    return 0;
}

Output

Constructed Tree is (Inorder Traversal):
4 2 5 1 6 3 7

Java Programming

import java.util.HashMap;
import java.util.Map;
 
// Class for a node
// having an integer value, data
// and two pointers
// to store the references of the
// left and right children
class Node
{
    int data;
    Node left, right;
 
    Node(int data) {
        this.data = data;
    }
}
 
class Main
{
    // function to print the 
	// constructed tree.
    public static void printTree(Node root)
    {
        if (root == null) {
            return;
        }
 
        printTree(root.left);
        System.out.print(root.data + " ");
        printTree(root.right);
    }
 
    // function to build a binary tree
	// from the given 2 arrays of integers, 
	// inorder & level order.
    public static Node constructBinaryTree(int[] inorder, int start, int end,
                                Map<Integer, Integer> map)
    {
        // base case
        if (start > end) {
            return null;
        }
 
        // search for the index of the first element of the
		// level order array,  
		// in the inorder array.
        int index = start;
        for (int j = start + 1; j <= end; j++)
        {
            // search for the index of the first element of the
			// level order array,  
			// in the inorder array, as it's the root of the
			// tree.
            if (map.get(inorder[j]) < map.get(inorder[index])) {
                index = j;
            }
        }
 
        // create the root node of the desired tree
        Node root = new Node(inorder[index]);
 
        // create the left subtree of the desired tree.
        root.left = constructBinaryTree(inorder, start, index - 1, map);
 
       	// create the right subtree of the desired tree.
        root.right = constructBinaryTree(inorder, index + 1, end, map);
 
        // return root
        return root;
    }
 
    // function to build a binary tree
	// from the given 2 arrays of integers, 
	// inorder & level order.
    public static Node constructBinaryTree(int[] in, int[] level)
    {
		// map to search for the
		// index of any node in the level order array.
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            map.put(level[i], i);
        }
 
        // finally, return the constructed tree.
        return constructBinaryTree(in, 0, in.length - 1, map);
    }
 
    public static void main(String[] args)
    {
        int[] inorder = { 4, 2, 5, 1, 6, 3, 7 };
        int[] level    = { 1, 2, 3, 4, 5, 6, 7 };
 
        Node root = constructBinaryTree(inorder, level);
 
        System.out.println("Constructed Tree is (Inorder Traversal):");
        printTree(root);
        System.out.println();
    }
}

Output

Constructed Tree is (Inorder Traversal):
4 2 5 1 6 3 7

Python Programming

# Class for a node
# having an integer value, data
# and two pointers
# to store the references of the
# left and right children
class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
 
 
# function to print the 
# constructed tree.
def printTree(root):
 
    if root is None:
        return
 
    printTree(root.left)
    print(root.data, end=' ')
    printTree(root.right)
 
 
# function to build a binary tree
# from the given 2 arrays of integers, 
# inorder & level order.
def constructBinaryTree(inorder, start, end, dict):
 
    # base case
    if start > end:
        return None
 
    # search for the index of the first element of the
    # level order array,  
    # in the inorder array.
    index = start
    for j in range(start + 1, end + 1):
        # search for the index of the first element of the
        # level order array,  
        # in the inorder array, as it's the root of the
        # tree.
        if dict.get(inorder[j]) < dict.get(inorder[index]):
            index = j
 
    # create the root node of the desired tree
    root = Node(inorder[index])
 
    # create the left subtree of the desired tree.
    root.left = constructBinaryTree(inorder, start, index - 1, dict)
 
    # create the right subtree of the desired tree.
    root.right = constructBinaryTree(inorder, index + 1, end, dict)
 
    # return root 
    return root
 
 
# function to build a binary tree
# from the given 2 arrays of integers, 
# inorder & level order.
def constructBT(inorder, level):
 
    # dictionary to search for the
    # index of any node in the level order array.
    dict = {}
    for i, e in enumerate(level):
        dict[e] = i
 
    # finally, return the constructed tree.
    return constructBinaryTree(inorder, 0, len(inorder) - 1, dict)
 
 
if __name__ == '__main__':
 
    inorder = [4, 2, 5, 1, 6, 3, 7]
    level = [1, 2, 3, 4, 5, 6, 7]
 
    root = constructBT(inorder, level)
 
    print("Constructed Tree is (Inorder Traversal):")
    printTree(root)
    print()

Output

Constructed Tree is (Inorder Traversal):
4 2 5 1 6 3 7

Complexity Analysis

Time Complexity : O(n^2) where n is the number of nodes of the Binary Tree.

Wrapping Up!

In this article, we have learned an amazing concept of Binary Trees. Binary Trees are one of the most important data structures and are usually asked in the top interview questions as well. “Construct a Binary Tree from Inorder and Level Order traversals” is a popular as well as a very important problem that has been asked in various interview questions.

In this article, we have included proper examples with detailed explanations for a better understanding for you. We also learned about how we should think of a solution and then make optimizations in our code for such kinds of problems. We discussed two well-explained approaches along with some suitable examples to solve this problem.

Also, we covered in detail how both of the approaches work and what is the significance of all of them. We discussed their time complexity along with a proper explanation. Different programmers prefer different languages for coding. So, we made sure that all our readers could refer to this article.

That’s why this article also contains well-explained codes for all the approaches in the three most popular languages, which are c++, Java, and python, along with their respective outputs attached to the article for a better understanding of a wide range of our readers. We sincerely hope that this article has walked you through some deep and important concepts of Binary Trees and how we should approach such kinds of problems. We surely wish you to keep up your practice and crack all the questions easily. With this, we are wrapping up this article.

Happy Learning!

People are also reading:

• Breadth First Search- Graph: DSA
• Depth First Search(DFS)- DSA
• What is Shell Sort?
• What is Sorting?
• Queue Data Structure
• WAP in C++ & Python to find the largest & smallest element in Array
• What is Stack in Data?
• Circular Linked List
• Doubly Linked List
• Linked List