Check if given inorder and preorder traversals are valid for any Binary Tree without building the tree

Debarati Ghatak
Last Updated: May 13, 2022

Introduction

In this problem, we have to check whether the given inorder and preorder traversals are valid for a binary tree or not. But the catch here is that we cannot build a binary tree to check if the traversals are valid! 

Problem Statement

Check if given inorder and preorder traversals are valid for any Binary Tree without building the tree

Test Case

Input: Inorder Array and Preorder Array are given as input,

 

 

Output:

Yes

 

First let us understand how to construct a binary tree if inorder and preorder traversals are given. 

Constructing a binary tree from given inorder and preorder tree traversal

Approach

Let us consider the following inorder and preorder traversal array for a binary tree,

Inorder[] = [40,20,50,10,30]

Preorder[] = [10,20,40,50,30]

In the case of Inorder traversal, we traverse the tree following this pattern:

  • Left
  • Root
  • Right

In the case of Preorder traversal, we traverse the tree following this pattern:

  • Root
  • Left
  • Right

If the Preorder traversal of the tree is given, the first element in the traversal will always be the root. So in our example, where the preorder array is,

Preorder[] = [10,20,40,50,30]

The root is 10. 

But with the help of only preorder traversal alone, we can not understand which elements lie in the left subtree and right subtree of the root. So we need to take the help of the inorder array. 

Inorder[] = [40,20,50,10,30]

Element 10 lies in the third index of the inorder array. So, therefore, everything to the left of 10 (i.e. from index 0 to 2) should lie in the left subtree of 10. Similarly, everything to the right of 10 in the array (i.e. index 4) should lie in the right subtree.

 

But how will we know what should be the root of the left and right subtree? For that, we have to look at the next element in the preorder traversal array. The next element in the preorder traversal array is the root of the left subtree (if the left subtree exists).

 

The next element in the preorder traversal array is 20.

Preorder[] = [10,20,40,50,30]

Therefore the root of the left subtree is 20.
 

Now to know what comes in the left and right subtree of 20, we again take the help of an inorder traversal array. 

Inorder[] = [40,20,50,10,30]

20 lies in index 1 and elements to the left of it lie in the left subtree, and element to it’s right lies in the right subtree. So 40 should be the left child, and 50 should be the right child of 20.

 

Now that we are done with the entire left subtree, let’s build the right subtree. As element 30 is the only node left, it connects to the root 10.

Our final constructed binary tree is.
 

 

While building the tree, we can notice a recursive pattern in the above steps, and we can all the steps to build the binary tree. 

We are essentially doing a preorder traversal of the tree, and building the tree with the help of the inorder array.

Steps of Algorithm

Initialize preorder_index as 0

  1. Take the element corresponding to the current preorder_index.
  2. Create a new tree node with the data at preorder_index.
  3. Increment the preorder_index by 1.
  4. Find the inorder_index for the element present at the preorder_index.
  5. Repeat the above steps for elements to the left of inorder_index, and connect the built tree as the left subtree of the current node.
  6. Repeat the above steps for elements to the right of inorder_index, and connect the built tree as the right subtree of the current node.
  7. Return the node.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
// Initializing preorder_index as 0
int preorder_index = 0;

// Structure of Node
struct Node
{
   int data;
   Node *left;
   Node *right;
   Node(int x)
   {
       data = x;
       left = right = NULL;
   }
};

// Inorder Traversal
void inorderTraversal(Node *root)
{
   if (root == NULL)
       return;
   inorderTraversal(root->left);
   cout << root->data << " ";
   inorderTraversal(root->right);
}

// Construct the binary tree
Node *construct(int inorder_arr[], int preorder_arr[], int inorder_start, int inorder_end)
{
   // If inorder_start and inorder end indicates the current segment of inorder array, which is explored
   // inorder_start indicates the start of that segment
   // inorder_end indicates the end of that segment
   // If inorder_start index is greater than inorder_end return NULL
   if (inorder_start > inorder_end)
       return NULL;

   // Create a new node and assign it the value of element at preorder_index
   // Increment preorder index by one
   Node *root = new Node(preorder_arr[preorder_index]);
   preorder_index++;
 
   int inorder_index;

   // Search the index of the newly created node in the inorder array
   for (int i = inorder_start; i <= inorder_end; i++)
   {
       if (inorder_arr[i] == root->data)
       {
           inorder_index = i;
           break;
       }
   }

   // Connect the left subtree to the current node
   root->left = construct(inorder_arr, preorder_arr, inorder_start, inorder_index - 1);
   // Connect the right subtree to the current node
   root->right = construct(inorder_arr, preorder_arr, inorder_index + 1, inorder_end);

   // Finally return the root
   return root;
}

int main()
{
   int inorder_arr[] = {40, 20, 50, 10, 30};
   int preorder_arr[] = {10, 20, 40, 50, 30};
   Node *root = construct(inorder_arr, preorder_arr, 0, 4);
   cout << "The inorder traversal of the constructed binary tree is:" << endl;
   inorderTraversal(root);
   return 0;
}

 

Output:

The inorder traversal of the constructed binary tree is:
40 20 50 10 30

 

Complexity Analysis

Time Complexity: O(n2) here we are essentially doing a preorder traversal of the tree, and the traversal takes O(n) time. We are doing extra O(n) work for each node, when we search for the node in the inorder array using a for loop. So the total time complexity becomes O(n2).

Space Complexity: O(h) as we are using recursion for the tree traversal. Here h refers to the height of the tree.

 

Efficient Approach

We can make our code more efficient by using an unordered map instead of searching inorder_index every time. The unordered_map will store data of nodes along with their corresponding inorder array index. 

With this unordered_map, we can now search the inorder_index in O(1) time instead of O(n) time. Therefore, the code below has a time complexity of O(n), which is better than our previous solution.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
// Initializing preorder_index as 0
int preorder_index = 0;

// Structure of Node
struct Node
{
   int data;
   Node *left;
   Node *right;
   Node(int x)
   {
       data = x;
       left = right = NULL;
   }
};

// Inorder Traversal
void inorderTraversal(Node *root)
{
   if (root == NULL)
       return;
   inorderTraversal(root->left);
   cout << root->data << " ";
   inorderTraversal(root->right);
}

// Construct the binary tree
Node *construct(unordered_map<int, int>& inorder_map, int preorder_arr[], int inorder_start, int inorder_end)
{
   // If inorder_start and inorder end indicates the current segment of inorder array, which is explored
   // inorder_start indicates the start of that segment
   // inorder_end indicates the end of that segment
   if (inorder_start > inorder_end)
       return NULL;

   // Create a new node and assign it the value of element at preorder_index
   // Increment preorder_index by one
   Node *root = new Node(preorder_arr[preorder_index]);
   preorder_index++;

   int inorder_index;

   // Find the index of the newly created node in the inorder_map
   inorder_index = inorder_map[root->data];
 
   // Connect the left subtree to the current node
   root->left = construct(inorder_map, preorder_arr, inorder_start, inorder_index - 1);
   // Connect the right subtree to the current node
   root->right = construct(inorder_map, preorder_arr, inorder_index + 1, inorder_end);

   // Finally return the root
   return root;
}

int main()
{
   int inorder_arr[] = {40, 20, 50, 10, 30};
   int preorder_arr[] = {10, 20, 40, 50, 30};
   int n = 5;

   // inorder_map stores data of nodes along with their inorder array index
   unordered_map<int, int> inorder_map;
   for (int i = 0; i < n; i++)
       inorder_map[inorder_arr[i]] = i;

   Node *root = construct(inorder_map, preorder_arr, 0, n-1);
   cout << "The inorder traversal of the constructed binary tree is:" << endl;
   inorderTraversal(root);
   return 0;
}

 

Complexity Analysis

Time Complexity: O(n) as we are using an unordered map to directly find the inorder index

Space Complexity: O(h) as we are using recursion for the tree traversal. Here h refers to the height of the tree.

Checking the validity of given inorder and preorder traversals for a binary tree

Approach

Now that we understand how to construct a tree when inorder and preorder traversals are given, let us come back to our original problem.

We will use the same approach that we used to construct the binary tree to solve this problem. But instead of building the tree, we will do a preorder traversal of the tree, like we did before and check if the traversals are valid or invalid.

For checking whether the traversals are valid or not, we will do the following

  • We will check whether the current element at preoder_index is present in the inorder array or not.
  • We will check whether the inorder_index lies within the inorder_start and inorder_end range, if it does not we will return false.
  • We will recursively check the above conditions for the left and right subtrees.

Steps of Algorithm

Initialize preorder_index as 0

  • If (inorder_start inorder_end)
    • return false
  • Assign root the value of the element corresponding to preorder_index.
  • Increment the preorder_index by 1.
  • If root is not present in inorder array
    • return false
  • Find out the inorder_index of the root using map.
  • If inorder_index does not lie within inorder_start and inorder_end range, 
    • return false
  • Repeat the above steps for elements to the left of inorder_index, and check if left subtree can be built using the inorder traversal.
  • Repeat the above steps for elements to the right of inorder_index, and check if right subtree can be built using the inorder traversal.

Implementation in C++

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

// Initializing preorder_index as 0
int preorder_index = 0;

bool check(int inorder_start, int inorder_end, int preorder_arr[], unordered_map<int, int> &inorder_map)
{
	if (inorder_start > inorder_end)
	return true;

	// Make the current element at preorder_index as root
	// Increment preorder_index by one
	int root = preorder_arr[preorder_index];
	preorder_index++;

	// If root is not present in inorder array, traversals are invalid
	if (inorder_map.find(root) == inorder_map.end())
		return false;

	// Get the inorder_index from map
	int inorder_index = inorder_map[root];

	// If inorder_index does not lie within inorder_start and inorder_end, traversals are invalid
	if (inorder_start > inorder_index and inorder_index > inorder_end)
	return false;

	// Inorder_start_left and inorder_end_left are the start and end indices of left subtree of root
	int inorder_start_left = inorder_start;
	int inorder_end_left = inorder_index - 1;
	// Inorder_start_right and inorder_end_right are the start and end indices of right subtree of root
	int inorder_start_right = inorder_index + 1;
	int inorder_end_right = inorder_end;

	// If left subtree can not be built, return false (no need to check for right subtree)
	if (!check(inorder_start_left, inorder_end_left, preorder_arr, inorder_map))
		return false;
	// If right subtree can not be built, return false
	else
		return check(inorder_start_right, inorder_end_right, preorder_arr, inorder_map);
}

int main()
{
	int inorder_arr[] = {40, 20, 50, 10, 30};
	int preorder_arr[] = {10, 20, 40, 50, 30};
	int n = 5;
	unordered_map<int, int> inorder_map;
	for (int i = 0; i < n; i++)
		inorder_map[inorder_arr[i]] = i;

	if (check(0, n - 1, preorder_arr, inorder_map))
	cout << "Yes" << endl;
	else
	cout << "No" << endl;
	return 0;
}

 

Output:

Yes

 

Complexity Analysis

Time Complexity: O(n) as we are essentially doing a preorder traversal of the tree using the preorder array. Here ‘n’ refers to the number of nodes in the tree.

Space Complexity: O(h) as we are using recursion for the tree traversal. Here ‘h’ refers to the height of the tree.

Frequently Asked Questions

Q1 Can we construct a binary tree using any two traversals of the tree?

Ans: No, we cannot construct a binary tree using ‘any’ two traversals of the tree. We need the inorder traversal of the binary tree, along with preorder or postorder traversal. Because with preorder and postorder traversal, more than one binary tree can get generated due to ambiguity.

However, if the tree is a full Binary tree, we will be able to construct a unique tree using only preorder and postorder traversal.

 

Q2 How to know which is the root node from the preorder traversal of a tree?

Ans: The first element in a preorder traversal of a tree is always the root of the tree.

In the case of preorder traversal, the root is visited first followed by the left subtree and then the right subtree.

 

Q3 What is unordered_map STL in C++?

Ans: Unordered maps are containers that store elements as key-value pairs. The ‘key’ is used to uniquely identify a ‘value’ for each key-value pair. 

Unordered maps are internally implemented using hash tables, and as its name suggests, the data is stored in an unordered fashion.

 

Q4 What is the time complexity of the various operations performed by unordered_map in C++?

Ans: Unordered_map is a very handy and fast data structure in C++. The average time complexity of operations like insert, search and delete with unordered_map is O(1).

Key Takeaways

In this blog, we learned how to approach and solve the given question. We first understood how to construct a binary tree if two tree traversals are given. We then solved the given problem using the same method for constructing the binary tree.

If you wish to master Tree data structure, then we have got you covered. Read this amazing blog to know more!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think