Construct a Tree with Inorder and Preorder Traversal

Let's start by understanding the problem statement to Construct a Tree with Inorder and Preorder Traversal.

You are given an inorder and a preorder traversal array, you need to construct a tree from the given array traversals.

Hint:

Now if we give a closer look at the difficulty and recall the preorder and inorder traversals of the tree we can clearly see that in preorder traversal the sequence is first the node data value gets printed, and then its left child followed by its right child data value and in the case of inorder traversal, the sequence is the left child of the node and then the node followed by its right child node data value. So from this if we think carefully we get to know that the data values in the preorder traversal array will be the root node and all the data values before the index value of the same data value in the inorder array will be its left child node, and after it will be the right child node of the data value in the preorder array traversal.

Quick Think:

For creating a tree out of the inorder and the preorder traversals, you need to think about the following points in mind:

1. The starting index must be smaller than the last index of the preorder and inorder array traversals, if it is larger than the last index then we will return NULL as this case is not possible.

2. If the starting index of the preorder array is equal to the last index it means the node is present in the same index from the last and the start of the array and hence returns the node which will be the base case of our recursive function.

3. An index pointer to keep track of the index of the next node in the preorder traversal array.

Algorithm:

We will create a recursive function with arguments as the preorder array traversal, index of the next parent node, start index and the end index, and the inorder array traversal then the following steps are to be performed:-

Step 1: We will check the condition that whether the start index of the preorder and inorder array traversals is greater than the last index of both the arrays if it is ‘True’ then return NULL else go to step 2.

Step 2: Define a temporary array to store the newly created node for the tree formation, where the data values from the preorder array traversal are passed for the creation of new nodes.

Step 3: Increment the value of the array index each time the new node is created.

Step 4: Check for the condition that the start and the end index of both the array traversals are equal if equal then return the newly created node to the tree, else go to step 5.

Step 5: Now search for the index of the newly created node in the inorder array traversal and, if found, return the index to the variable defined to store the index of the parent node data value.

Step 6: Now for the left child node of the parent node so formed a recursive call to the function is created with the arguments as the preorder traversal array, index to the next parent node, start, and the variable which has the parent node index – 1 index and the inorder array traversal.

Step 7: Similarly for the right child node of the parent node so created a recursive call to the function is created with the arguments as the preorder traversal array, index of the next parent node, a variable which has the index of the parent node + 1 index, the end index and the inorder array traversal.

Step 8: Return the node so formed.

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 = NULL;
	struct node *right = NULL;
};

/*Function to return the newly created array. */
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 check for the index of the parent node in the inorder traversal array. */
int searchnode(int in[], int start, int end, int data)
{
	for (int i = start; i <= end; i++)
	{
		if (in[i] == data)
			return i;
	}
}

/*Function to return the newly created node along with the it's left and the right child node using the preorder array traversal. */
struct node* create_tree(int in[], int pre[], int *index, int start, int end)
{
	if (start > end)
		return NULL;
	struct node *temp = newnode(pre[*index]) *
		index = *index + 1;
	if (start == end)
		return temp;
	int search = searchnode(in, start, end, temp->data);
	temp->left = create_tree(in, pre, index, start, search - 1);
	temp->right = create_tree(in, pre, index, search + 1, end);
	return temp;
}

void inorder(struct node *root)
{
	if (root == NULL)
		return NULL;
	inorder(root->left);
	cout << root->data << " ";
	inorder(root->right);
}

/*Driver function to check the above algorithm. */
int main()
{
	int in[] = { 1, 2, 3, 4, 5, 6 };

	int pre[] = { 4, 2, 1, 3, 6, 5 };

	int len = sizeof(in) / sizeof(in[0]);
	int index = 0;
	struct node *root = create_tree(in, pre, &index, 0, len - 1);

	/*Let us test the built tree by printing Inorder traversal */
	printf("Inorder traversal of the constructed tree is \n");
	inorder(root);
	return 0;
}

The Running Time Complexity Of The above Algorithm is O(n^2).
The Output Of The Above Code is :
Inorder traversal of the constructed tree is 1 2 3 4 5 6.

Explanation Of The Above Algorithm:

Let us consider two array traversals of inorder traversal and preorder traversal such as in[ ] = {1, 2, 3, 4, 5, 6} and pre[ ] = {4, 2, 1, 3, 6, 5} respectively as shown in the above diagram and perform the following operations to create a tree.

1. From the hint above, we can recall that the first array element of the preorder array traversal is the root node for the tree to be constructed, hence here 4 is the root of the required tree as shown in the above diagram.

2. Now, since the start and the end of the array are the same, hence the node is returned as the root node of the required tree.

3. Now for the left child node of the parent node, we will search the inorder array traversal and find the index of the root node because to the left of the index, we will have our left child nodes and to the right of the root node we will have the right child node of the required tree, hence the next left child node according to the preorder array traversal the next node is 2, now the node with data 2 is searched for in the inorder array traversal and the index found is 1 now, for the left child of the node with data 2 is recursively called due to which the start and end index becomes equal and the node with data 2 is returned which becomes the left child node of 4 as shown in the above diagram.

4. Now similarly for the left child node of 2 from the inorder array traversal we have 1 at the left of the array element 2, and also now the start and the end index of the arrays are equal, hence 1 is returned as the left child of the node with data value 2 as shown in the above diagram.

5. Now the left child node of the parent node with data value 1 is recursively called but, now the start index of the arrays is greater than the end index hence the program returns NULL and there is no left child node of 1.

6. Similarly, in the case of the right child of the parent node with data value 1 the value NULL is returned and hence there is no right child of the parent node with data value 1.

7. Now the recursive call returns back to the node with data value 2, now the right child node of the parent node with data value 2 will be 3 as the start and end index are equal at this place, hence 3 is the right child of the parent node with data value 2 as shown in the diagram above.

8. Now the recursive call returns back to the right subtree of the parent node with data value 4.

9. Now since the next element in the preorder array traversal is 6 so, we will search for the index of this in our inorder array traversal, and we see that the left child node of the parent node with data value 6 is 5 as the start index of the array is equal to the end index of the array as shown in the given diagram above.

And in this way, our required tree is constructed from the inorder and the preorder array traversals.