Construct a tree from Inorder and Level order traversals

Posted in

Construct a tree from Inorder and Level order traversals
vinaykhatri

Vinay Khatri
Last updated on May 22, 2024

    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:

    Leave a Comment on this Post

    0 Comments