Construct a Binary Tree from Inorder and Preorder traversals

Posted in

Construct a Binary Tree from Inorder and Preorder traversals
vinaykhatri

Vinay Khatri
Last updated on May 22, 2024

    You are given inorder and preorder 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.

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

    Example 1:

    Input: 
    preorder = [3,9,20,15,7], 
    inorder = [9,3,15,20,7]
    Output: [3,9,20,null,null,15,7]
    

    Explanation: As we already know that the first element of the preorder array is the root node. Therefore, 3 will be the root of the tree. Then, we can get the elements of the left subtree by simply searching 3 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 3 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 preorder 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. Take the first element of the preorder array, which will be the root node.
    2. Create a new node as tNode and pass the element taken in the first step as the data.
    3. Iterate over the inorder array to find the index of the picked element. Let the index be inIndex.
    4. Make a function buildTree. The elements before the picked element will fall under the left subtree.
    5. The elements after the picked element will fall under the right subtree.
    6. Return tNode.

    The implementation of the above-discussed approach is:

    C++ Programming

    #include<bits/stdc++.h>
    using namespace std;
    
    // Class for a node
    // having an integer value, data
    // and two pointers
    // to store the references of the
    // left and right children
    class node
    {
    	public:
    	char data;
    	node* left;
    	node* right;
    };
    
    // declaring prototypes of the methods to be used
    int findIndex(char arr[], int strt, int end, char value);
    node* newNode(char data);
    
    // method to build a binary tree
    // from the given 2 arrays of integers, 
    // inorder & preorder. 
    node* constructBinaryTree(char in[], char pre[], int inStrt, int inEnd)
    {
    	static int preIndex = 0;
    
    	if (inStrt > inEnd)
    		return NULL;
    
    	// create a new node and 
    	// assign it the value of the current node
    	// using the preIndex.
    	// Update the preIndex variable
    	// so that it can be used for next recursive calls.
    	node* tNode = newNode(pre[preIndex++]);
    
    	// return if the new created node does not have children.
    	if (inStrt == inEnd)
    		return tNode;
    
    	// otherwise, compute its height
    	// in the inorder traversal.
    	int inIndex = findIndex(in, inStrt, inEnd, tNode->data);
    
    	// build left and right subtrees, with the help of 
    	// inIndex in the inorder array.
    	tNode->left = constructBinaryTree(in, pre, inStrt, inIndex - 1);
    	tNode->right = constructBinaryTree(in, pre, inIndex + 1, inEnd);
    
    	return tNode;
    }
    
    // defining the method findIndex,
    // that searches the index of the given 
    // value, passed as the parameter.
    int findIndex(char arr[], int strt, int end, char value)
    {
    	int i;
    	for (i = strt; i <= end; i++) { if (arr[i] == value) return i; } return i; } // method 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(char data) { node* Node = new node(); Node->data = data;
    	Node->left = NULL;
    	Node->right = NULL;
    
    	return (Node);
    }
    
    // method to print the 
    // constructed tree.
    void printTree(node* node)
    {
    	if (node == NULL)
    		return;
    
    	// recursively print the left subtree
    	printTree(node->left);
    
    	// print the root data
    	cout<data<<" "; // recursively print the right subtree printTree(node->right);
    }
    
    /* Driver code */
    int main()
    {
    	char in[] = { 'D', 'B', 'E', 'A', 'F', 'C' };
    	char pre[] = { 'A', 'B', 'D', 'E', 'C', 'F' };
    	int len = sizeof(in) / sizeof(in[0]);
    	node* root = constructBinaryTree(in, pre, 0, len - 1);
    
    	cout << "Constructed Tree is (Inorder Traversal): \n";
    	printTree(root);
    }

    Output

    Constructed Tree is (Inorder Traversal): 
    D B E A F C

    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 {
    	char data;
    	Node left, right;
    
    	Node(char item)
    	{
    		data = item;
    		left = right = null;
    	}
    }
    
    class BinaryTree {
    	Node root;
    	static int preIndex = 0;
    
    	// function to build a binary tree
    	// from the given 2 arrays of integers, 
    	// inorder & preorder.
    	Node constructBinaryTree(char in[], char pre[], int inStrt, int inEnd)
    	{
    		if (inStrt > inEnd)
    			return null;
    
    		// create a new node and 
    		// assign it the value of the current node
    		// using the preIndex.
    		// Update the preIndex variable
    		// so that it can be used for next recursive calls
    		Node tNode = new Node(pre[preIndex++]);
    
    		// return if the new created node does not have children.
    		if (inStrt == inEnd)
    			return tNode;
    
    		// otherwise, compute its height
    		// in the inorder traversal.
    		int inIndex = findIndex(in, inStrt, inEnd, tNode.data);
    
    		// build left and right subtrees, with the help of 
    		// inIndex in the inorder array.
    		tNode.left = constructBinaryTree(in, pre, inStrt, inIndex - 1);
    		tNode.right = constructBinaryTree(in, pre, inIndex + 1, inEnd);
    
    		return tNode;
    	}
    
    	// defining the function findIndex,
    	// that searches the index of the given 
    	// value, passed as the parameter.
    	int findIndex(char arr[], int strt, int end, char value)
    	{
    		int i;
    		for (i = strt; i <= end; i++) {
    			if (arr[i] == value)
    				return i;
    		}
    		return i;
    	}
    
    
    	// function to print the 
    	// constructed tree.
    	void printTree(Node node)
    	{
    		if (node == null)
    			return;
    
    		// recursively print the left subtree
    		printTree(node.left);
    
    		// print the root data
    		System.out.print(node.data + " ");
    
    		// recursively print the right subtree
    		printTree(node.right);
    	}
    
    	public static void main(String args[])
    	{
    		BinaryTree tree = new BinaryTree();
    		char in[] = new char[] { 'D', 'B', 'E', 'A', 'F', 'C' };
    		char pre[] = new char[] { 'A', 'B', 'D', 'E', 'C', 'F' };
    		int len = in.length;
    		Node root = tree.constructBinaryTree(in, pre, 0, len - 1);
    
    		System.out.println("Constructed Tree is (Inorder Traversal): ");
    		tree.printTree(root);
    	}
    }

    Output

    Constructed Tree is (Inorder Traversal): 
    D B E A F C

    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):
    		self.data = data
    		self.left = None
    		self.right = None
    
    # function to build a binary tree
    # from the given 2 arrays of integers, 
    # inorder & preorder.
    def constructBinaryTree(inOrder, preOrder, inStrt, inEnd):
    	
    	if (inStrt > inEnd):
    		return None
    
    	# create a new node and 
    	# assign it the value of the current node
    	# using the preIndex.
    	# Update the preIndex variable
    	# so that it can be used for next recursive calls
    	tNode = Node(preOrder[constructBinaryTree.preIndex])
    	constructBinaryTree.preIndex += 1
    
    	# return if the new created node does not have children.
    	if inStrt == inEnd :
    		return tNode
    
    	# otherwise, compute its height
    	# in the inorder traversal.
    	inIndex = findIndex(inOrder, inStrt, inEnd, tNode.data)
    	
    	# build left and right subtrees, with the help of 
    	# inIndex in the inorder array.
    	tNode.left = constructBinaryTree(inOrder, preOrder, inStrt, inIndex-1)
    	tNode.right = constructBinaryTree(inOrder, preOrder, inIndex + 1, inEnd)
    
    	return tNode
    
    # defining the function findIndex,
    # that searches the index of the given 
    # value, passed as the parameter.
    def findIndex(arr, start, end, value):
    	for i in range(start, end + 1):
    		if arr[i] == value:
    			return i
    # function to print the 
    # constructed tree.
    def printTree(node):
    	if node is None:
    		return
    	
    	# recursively print the left subtree
    	printTree(node.left)
    	
    	# print the root data
    	print (node.data, end = " ")
    
    	# recursively print the right subtree
    	printTree(node.right)
    	
    # Driver program 
    inOrder = ['D', 'B', 'E', 'A', 'F', 'C']
    preOrder = ['A', 'B', 'D', 'E', 'C', 'F']
    
    constructBinaryTree.preIndex = 0
    root = constructBinaryTree(inOrder, preOrder, 0, len(inOrder)-1)
    
    
    print ("Constructed Tree is (Inorder Traversal):")
    printTree(root)

    Output

    Constructed Tree is (Inorder Traversal): 
    D B E A F C

    C# Programming

    using System;
    
    // Class for a node
    // having an integer value, data
    // and two pointers
    // to store the references of the
    // left and right children
    public class Node {
    	public char data;
    	public Node left, right;
    
    	public Node(char item)
    	{
    		data = item;
    		left = right = null;
    	}
    }
    
    public class Tree {
    	public static Node root;
    	public static int preIndex = 0;
    
    	// function to build a binary tree
    	// from the given 2 arrays of integers, 
    	// inorder & preorder. 
    	public virtual Node convertBinaryTree(char[] arr, char[] pre,
    								int inStrt, int inEnd)
    	{
    		if (inStrt > inEnd) {
    			return null;
    		}
    
    		// create a new node and 
    		// assign it the value of the current node
    		// using the preIndex.
    		// Update the preIndex variable
    		// so that it can be used for next recursive calls.
    		Node tNode = new Node(pre[preIndex++]);
    
    		// return if the new created node does not have children.
    		if (inStrt == inEnd) {
    			return tNode;
    		}
    
    		// otherwise, compute its height
    		// in the inorder traversal.
    		int inIndex = findIndex(arr, inStrt,
    							inEnd, tNode.data);
    
    		// build left and right subtrees, with the help of 
    		// inIndex in the inorder array.
    		tNode.left = convertBinaryTree(arr, pre, inStrt, inIndex - 1);
    		tNode.right = convertBinaryTree(arr, pre, inIndex + 1, inEnd);
    
    		return tNode;
    	}
    
    	// defining the function findIndex,
    	// that searches the index of the given 
    	// value, passed as the parameter.
    	public virtual int findIndex(char[] arr, int strt,
    							int end, char value)
    	{
    		int i;
    		for (i = strt; i <= end; i++) {
    			if (arr[i] == value) {
    				return i;
    			}
    		}
    		return i;
    	}
    
    	// function to print the 
    	// constructed tree.
    	public virtual void printTree(Node node)
    	{
    		if (node == null) {
    			return;
    		}
    
    		// recursively print the left subtree
    		printTree(node.left);
    
    		// print the root data
    		Console.Write(node.data + " ");
    
    		// recursively print the right subtree
    		printTree(node.right);
    	}
    
    	public static void Main(string[] args)
    	{
    		Tree tree = new Tree();
    		char[] arr = new char[] { 'D', 'B', 'E', 'A', 'F', 'C' };
    		char[] pre = new char[] { 'A', 'B', 'D', 'E', 'C', 'F' };
    		int len = arr.Length;
    		Node root = tree.convertBinaryTree(arr, pre, 0, len - 1);
    
    		Console.WriteLine("Constructed Tree is (Inorder Traversal):");
    		tree.printTree(root);
    	}
    }

    Output

    Constructed Tree is (Inorder Traversal): 
    D B E A F C

    Complexity Analysis

    Time Complexity : O(n) where n is the number of nodes of the Binary Tree. We are simply linearly iterating the tree

    Approach 2

    This approach is more optimized than the previous one. We will be using hashing in this method to store the indices.

    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. Create a new node and assign it the value of the current node using the preIndex.
    3. Update the preIndex variable so that it can be used for the next recursive calls.
    4. Return if the newly created node does not have children.
    5. Otherwise, compute its height in the inorder traversal.
    6. Build left and right subtrees with the help of inIndex in the inorder array.

    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 {
    	char data;
    	struct Node* left;
    	struct Node* 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
    struct Node* newNode(char data)
    {
    	struct Node* node = new Node;
    	node->data = data;
    	node->left = node->right = NULL;
    	return (node);
    }
    
    // function to build a binary tree
    // from the given 2 arrays of integers, 
    // inorder & preorder.
    struct Node* convertBinaryTree(char in[], char pre[], int inStrt,
    					int inEnd, unordered_map<char, int>& mp)
    {
    	static int preIndex = 0;
    
    	if (inStrt > inEnd)
    		return NULL;
    
    	// create a new node and 
    	// assign it the value of the current node
    	// using the preIndex.
    	// Update the preIndex variable
    	// so that it can be used for next recursive calls.
    	char curr = pre[preIndex++];
    	struct Node* tNode = newNode(curr);
    
    	// return if the new created node does not have children.
    	if (inStrt == inEnd)
    		return tNode;
    
    	// otherwise, compute its height
    	// in the inorder traversal.
    	int inIndex = mp[curr];
    
    	// build left and right subtrees, with the help of 
    	// inIndex in the inorder array.
    	tNode->left = convertBinaryTree(in, pre, inStrt, inIndex - 1, mp);
    	tNode->right = convertBinaryTree(in, pre, inIndex + 1, inEnd, mp);
    
    	return tNode;
    }
    
    // wrapper function for the convertBinaryTree function 
    // that creates a map 
    struct Node* convertBinaryTreeWrap(char in[], char pre[], int len)
    {
    	// hold the indices of all elements in
    	// the unorderd map.
    	unordered_map<char, int> mp;
    	for (int i = 0; i < len; i++) mp[in[i]] = i; return convertBinaryTree(in, pre, 0, len - 1, mp); } // function to print the // constructed tree. void printTree(struct Node* node) { if (node == NULL) return; printTree(node->left);
    	cout << node->data << " "; printTree(node->right);
    }
    
    int main()
    {
    	char in[] = { 'D', 'B', 'E', 'A', 'F', 'C' };
    	char pre[] = { 'A', 'B', 'D', 'E', 'C', 'F' };
    	int len = sizeof(in) / sizeof(in[0]);
    
    	struct Node* root = convertBinaryTreeWrap(in, pre, len);
    
    	cout << "Constructed Tree is (Inorder Traversal): \n";
    	printTree(root);
    }

    Output

    Constructed Tree is (Inorder Traversal): 
    D B E A F C

    Java Programming

    import java.io.*;
    import java.util.*;
    
    // Class for a node
    // having an integer value, data
    // and two pointers
    // to store the references of the
    // left and right children
    class Node
    {
    char data;
    Node left,right;
    Node(char item)
    {
    	data = item;
    	left = right = null;
    }
    }
    class Tree
    {
    
    public static Node root;
    
    // hold the indices of all elements in
    // the unorderd map.
    static HashMap<Character,Integer> mp = new HashMap<>();
    static int preIndex = 0;
    
    // function to build a binary tree
    // from the given 2 arrays of integers, 
    // inorder & preorder.
    public static Node convertBinaryTree(char[] in, char[] pre, int inStrt, int inEnd)
    {
    
    	if(inStrt > inEnd)
    	{
    	return null;
    	}
    
    	// create a new node and 
    	// assign it the value of the current node
    	// using the preIndex.
    	// Update the preIndex variable
    	// so that it can be used for next recursive calls.
    	char curr = pre[preIndex++];
    	Node tNode;
    	tNode = new Node(curr);
    
    	// return if the new created node does not have children.
    	if (inStrt == inEnd)
    	{
    	return tNode;
    	}
    
    	// otherwise, compute its height
    	// in the inorder traversal.
    	int inIndex = mp.get(curr);
    
    	// build left and right subtrees, with the help of 
    	// inIndex in the inorder array.
    	tNode.left = convertBinaryTree(in, pre, inStrt, inIndex - 1);
    	tNode.right = convertBinaryTree(in, pre, inIndex + 1, inEnd);
    	return tNode;
    }
    
    // wrapper function for the convertBinaryTree function 
    // that creates a map 
    public static Node convertBinaryTreeWrap(char[] in, char[] pre, int len)
    {
    	for(int i = 0; i < len; i++)
    	{
    	mp.put(in[i], i);
    	}
    	return convertBinaryTree(in, pre, 0, len - 1);
    }
    
    // function to print the 
    // constructed tree.
    static 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)
    {
    	char[] in = {'D', 'B', 'E', 'A', 'F', 'C'};
    	char[] pre = {'A', 'B', 'D', 'E', 'C', 'F'};
    	int len = in.length;
    
    	Tree.root=convertBinaryTreeWrap(in, pre, len);
    
    	System.out.println("Constructed Tree is (Inorder Traversal):");
    	printTree(root);
    }
    }

    Output

    Constructed Tree is (Inorder Traversal): 
    D B E A F C

    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, x):
    		
    		self.data = x
    		self.left = None
    		self.right = None
    
    # function to build a binary tree
    # from the given 2 arrays of integers, 
    # inorder & preorder.
    def convertBinaryTree(inn, pre, inStrt, inEnd):
    	
    	global preIndex, mp
    
    	if (inStrt > inEnd):
    		return None
    
    	# create a new node and 
    	# assign it the value of the current node
    	# using the preIndex.
    	# Update the preIndex variable
    	# so that it can be used for next recursive calls.
    	curr = pre[preIndex]
    	preIndex += 1
    	tNode = Node(curr)
    
    	# return if the new created node does not have children.
    	if (inStrt == inEnd):
    		return tNode
    
    	# otherwise, compute its height
    	# in the inorder traversal.
    	inIndex = mp[curr]
    
    	# build left and right subtrees, with the help of 
    	# inIndex in the inorder array.
    	tNode.left = convertBinaryTree(inn, pre, inStrt,
    						inIndex - 1)
    	tNode.right = convertBinaryTree(inn, pre, inIndex + 1,
    							inEnd)
    
    	return tNode
    
    # wrapper function for the convertBinaryTree function 
    # that creates a map 
    def convertBinaryTreeWrap(inn, pre, lenn):
    	
    	global mp
    	
    	# hold the indices of all elements in
    	# the unorderd map.
    	for i in range(lenn):
    		mp[inn[i]] = i
    
    	return convertBinaryTree(inn, pre, 0, lenn - 1)
    
    # function to print the 
    # constructed tree.
    def printTree(node):
    
    	if (node == None):
    		return
    		
    	printTree(node.left)
    	print(node.data, end = " ")
    	printTree(node.right)
    
    # Driver code
    if __name__ == '__main__':
    	
    	mp = {}
    	preIndex = 0
    
    	inn = [ 'D', 'B', 'E', 'A', 'F', 'C' ]
    	pre = [ 'A', 'B', 'D', 'E', 'C', 'F' ]
    	lenn = len(inn)
    
    	root = convertBinaryTreeWrap(inn, pre,lenn)
    
    
    	print("Constructed Tree is (Inorder Traversal):")
    	
    	printTree(root)

    Output

    Constructed Tree is (Inorder Traversal): 
    D B E A F C

    C# Programming

    using System;
    using System.Collections.Generic;
    
    // Class for a node
    // having an integer value, data
    // and two pointers
    // to store the references of the
    // left and right children
    public class Node
    {
    	public char data;
    	public Node left, right;
    
    	public Node(char d)
    	{
    		data = d;
    		left = right = null;
    	}
    }
    public class Tree
    {
    	public static Node root;
    
    	// hold the indices of all elements in
    	// the unorderd map.
    	static Dictionary<char,int> mp = new Dictionary<char,int>();
    	static int preIndex = 0;
    
    	// function to build a binary tree
    	// from the given 2 arrays of integers, 
    	// inorder & preorder.
    	static Node convertBinaryTree(char[] In, char[] pre,
    						int inStrt, int inEnd)
    	{
    		if(inStrt > inEnd)
    		{
    			return null;
    		}
    	
    		// create a new node and 
    		// assign it the value of the current node
    		// using the preIndex.
    		// Update the preIndex variable
    		// so that it can be used for next recursive calls.
    		char curr = pre[preIndex++];
    		Node tNode;
    		tNode = new Node(curr);
    	
    		// return if the new created node does not have children.
    		if(inStrt == inEnd)
    		{
    			return tNode;
    		}
    	
    		// otherwise, compute its height
    		// in the inorder traversal.
    		int inIndex = mp[curr];
    	
    		// build left and right subtrees, with the help of 
    		// inIndex in the inorder array.
    		tNode.left = convertBinaryTree(In, pre, inStrt, inIndex - 1);
    		tNode.right = convertBinaryTree(In, pre, inIndex + 1, inEnd);
    		return tNode;
    	}
    
    	// wrapper function for the convertBinaryTree function 
    	// that creates a map 
    	public static Node convertBinaryTreeWrap(char[] In, char[] pre, int len)
    	{
    		for(int i = 0; i < len; i++)
    		{
    			mp.Add(In[i], i);
    		}
    		return convertBinaryTree(In, pre, 0, len - 1);
    	}
    
    	// function to print the 
    	// constructed tree.
    	static void printInorder(Node node)
    	{
    		if(node == null)
    		{
    			return;
    		}
    		printInorder(node.left);
    		Console.Write(node.data + " ");
    		printInorder(node.right);
    	}
    
    	static public void Main (){
    		char[] In = {'D', 'B', 'E', 'A', 'F', 'C'};
    		char[] pre = {'A', 'B', 'D', 'E', 'C', 'F'};
    		int len = In.Length;
    		Tree.root = convertBinaryTreeWrap(In, pre, len);
    	
    		Console.WriteLine("Constructed Tree is (Inorder Traversal):");
    		printInorder(Tree.root);
    	}
    }

    Output

    Constructed Tree is (Inorder Traversal): 
    D B E A F C

    Complexity Analysis:

    Time Complexity : O(n) 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 Preorder 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 also discussed two well-explained approaches along with some suitable examples to solve this problem. We also 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, C# 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