Construct a Tree from Inorder and Level Order Traversal

Let's start by understanding the problem statement of Constructing A Tree From Inorder And Level Order Traversal.

You are given an Inorder and a level order traversal, your work is to construct a tree using both the traversals.

Hint:

For creating a tree from inorder and level order traversals we need to think a bit about how to do it easily and quickly, so for this we may use two different arrays to store the left subtree and right subtree and keep taking values from it to create the tree and simultaneously removing the used values from it and at the end returning the complete tree so formed.

Quick Think:

For constructing a tree from inorder and level order traversal, we have a look into the following conditions:

1. We have to check for the size of both the arrays, if the size of the array is equal to or less than the value 0 then NULL has to be returned.

2. For storing the right subtree values into an array created we need to check to form the previous unordered set which will hold our left subtree, i.e., the values which are there in our unordered set should not be there in our right subtree array and simultaneously store the elements in the unordered set to our array containing the left subtree elements.

3. Here an unordered set is in use because it is known to contain all unique elements within itself which can be compared further to store the right subtree and the left subtree into two different arrays and also to determine the size of the left subarray to avoid space wastage, as an unordered set has a dynamic size allocation.

4. Declare two arrays, one to store the left subtree with the size same as that of the unordered set and the other to store the right subtree of the remaining size, to create the total size of the array.

5. A recursive function has to be defined for creating a new node for the left subtree and the right subtree.

Algorithm:

For creating a tree with the inorder and the level order traversal we will define a recursive function with the arguments as the inorder traversal array, the level order traversal array, the first index of the array, the last index, and the size of the array.

Step1: A condition is checked as the size of the array should not be less than 0 if this condition turns out to be ’True’ then NULL is returned else go to step 2.

Step2: A temporary node is declared to store the newly created node and search for the current node data value into the inorder array traversal and store the index of the data element in a variable.

Step3: Now since we know that in the inorder array traversal the elements on the left of the inorder traversal array are the elements in the left subtree, hence the elements from the start index to the index of the root data element in the inorder array traversal is stored in an unordered array to determine for the size of the left subtree array.

Step4: Declare an array with the size same as that of the unordered set to store the left subtree and the remaining size from the left out of the total size of the array, we will have our right subtree array.

Step5: Now we will keep inserting the inserted value in the unordered set except the first value (as it will be the leftmost extreme node of the required tree), to the left subtree array, and the non-inserted values to the right subtree array.

Step6: For creating the left child of the current node we need to pass arguments to the recursive function created above as the inorder array traversal, the left subtree array, the first index of the array, and the last index as the index of the root node in the inorder array – 1 and the total size of the left traversal array.

Step7: Now for creating the right subtree of the given root node we need to pass the arguments in the recursive function created above as the inorder array traversal, the right subtree array, the array index of root node data + 1, the last array index and the total size of the right subtree traversal array.

Step8: Return the root node.

Implementation Of The Above Algorithm:

Now let's see the implementation of the above algorithm,

#include <bits/stdc++.h>
using namespace std;
struct node
{
	int data;
	struct node *left, *right;
};

/*Function to return the newly created node. */
struct node* newnode(int data)
{
	struct node * node;
	node = (struct node *) malloc(sizeof(struct node));
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	return node;
}

/*Function to return the tree created from the inorder and the level order traversal. */
struct node* createtree(int in[], int level[], int start, int end, int n)
{
	int i;
	if (n <= 0)
		return NULL;
	struct node *root = newnode(level[0]);
	int index = -1;

	/*Finding the index of the data of the node in the inorder traversal array. */
	for (i = start; i <= end; i++)
	{
		if (level[0] == in[i])
		{
			index = i;
			break;
		}
	}

	/*Unordered set to keep a track of all elements of left subtree. */
	unordered_set<int> s;
	for (i = start; i < index; i++)
		s.insert(in[i]);
	int j = 0, k = 0;

	/*For storing the left subtree. */
	int llevel[s.size()];

	/*For storing the right subtree. */
	int rlevel[end - start - s.size()];
	for (i = 1; i < n; i++)
	{
		if (s.find(level[i]) != s.end())
			llevel[j++] = level[i];
		else
			rlevel[k++] = level[i];
	}

	/ *Returns the left subtree node. */
	root->left = createtree(in, llevel, start, index - 1, index - start);

	/*Returns the right subtree node. */
	root->right = createtree(in, rlevel, index + 1, end, end - index);
	return root;
}

/*Function to print the tree traversal. */
void printinorder(struct node *node)
{
	if (node == NULL)
		return;
	printinorder(node->left);
	cout << node->data << " ";
	printinorder(node->right);
}

/*Driver function to check the above algorithm. */
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]);
	struct node *root = createtree(in, level, 0,
		n - 1, n);

	/*Let us test the built tree by printing
	Inorder traversal */
	cout << "Inorder traversal of the "
	"constructed tree is \n";
	printinorder(root);

	return 0;

}

The time complexity of the above algorithm is O(n^2).
The output of the above code is :
Inorder traversal of the constructed tree is 4 8 10 12 14 20 22.

Explanation Of The Above Algorithm:

At the beginning let us take two array traversals one the inorder and the other the level order as shown in the above diagram, then we need to create a recursive function with the arguments as the inorder array, the level order array, the first index of the array, the last index of the array and the total size of the array. After defining a recursive function, we will follow the following steps:-

1. We will check the condition when the total size of the array is less than or equal to zero, then return NULL or skip the step.

2. Define a temporary node to store the first data of the level order traversal array as the parent node in each recursive call of the function. Now search for the index of the parent node data in the inorder array traversal, here we find it to be 'five'.

   

3. Now we will have the array for the left subtree of the root node in an unordered set except the node data at the first index (as it will be the leftmost extreme node of the required tree) and correspondingly the left subtree array and the right subtree array is created as shown in the above diagram.

4. Now for the left child of the parent node, we have the second element from the left subtree array i.e., 8 through a recursive function returning the arguments as the inorder array, level order array, the first index of the left subtree array, the last index of the left subtree array and it’s size.

5. Now, as the very first condition is false, the new node is created with data as 8.

6. Now the index of the new node is searched in the inorder traversal array and is returned to be ‘one’ and an unordered set is again created with only one element into it with data 4 initialize the size of both the arrays that are LLevel and the Rlevel.

   

7. Now for creating the left subtree and the right subtree array, we will traverse through the LLevel array (passed through an argument in the last recursion) from index 1 and see the elements present in the unordered set if present insert it to the LLevel array else insert it to the Rlevel array and both the arrays so formed are shown in the diagram.

   

8. Now again, since the LLevel array has only one element in the array, so we will return the left subtree as shown in the above figure.

9. Now for the right subtree of the node with data 8, we will call the recursive function created with the following arguments as the inorder traversal array, the RLevel traversal array, the first index of the Rlevel traversal array, the last index of the Rlevel array and the size of the RLevel array.

   

10. And similarly, the right subtree is created by a repeated recursive call of the functions, and the whole of the left subtree is formed as shown in the diagram above.

    

11. Now the recursive call again executes for the right subtree of the root node with data 20 and hence in step 3 we had a right subtree with a single data element so, that recursive step is invoked and the right subtree of the tree to be formed from the given inorder and the level order traversal is as shown in the diagram above.