Introduction
A Tree is a data structure which holds data in a hierarchical manner. It is also considered as a collection of nodes. A Binary Tree can be said as a special kind of Tree that can have the utmost 2 nodes as its children.
So, in this article we will cover the topic Constructing a Binary Tree from Two Traversal Sequences.
Problem Statement
Given Inorder Traversal and Preorder Traversal of a Binary Tree, construct the Binary Tree. The traversals will be given in the form of the array.
Sample Example
Input: Inorder traversal = {20, 10, 25, 5, 30, 15}, Preorder traversal = {5, 10, 20, 25, 15, 30}
Output: The constructed binary tree is
Explanation: The leftmost element of the Preorder traversal is the root of the binary tree. In the Inorder traversal sequence, the root element divides the sequence into the left and right subtrees. We can follow the previous step again to get the root of the subtrees and their child nodes.
Brute Force Approach
In the Preorder sequence, the first element is the root of the binary tree.
So, we start our tree from there. Then we find the root element in the Inorder sequence and use it to divide the elements into the left (i.e. all the elements to the left of the root) and right subtrees(i.e. all the elements to the right of the root). For the problem in the example above, it would look like this:
Using recursion, we can apply the previous step to each subtree until we get null children. In the end, we would have the following tree
Algorithm
- Initialize a variable that would keep track of the Preorder traversal element that we are considering. This is the Preorder Index, which will be incremented to pick up the next element. We start it from the leftmost element of the sequence, the root of the binary tree.
- Add the picked element from the Preorder traversal as a node to the binary tree.
- Find the picked element in the Inorder traversal and store its index in the sequence in the Inorder Index.
- Recursively call the algorithm for elements before the Inorder Index value. This will create subtrees within the left subtree.
- Recursively call the algorithm for elements after the Inorder Index value. This will create subtrees within the right subtree.
- Return the constructed binary tree.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
class node
{
public:
char data;
node* left;
node* right;
};
node* newNode(char data)
{
node* Node = new node();
Node->data = data;
Node->left = Node->right = NULL;
return(Node);
}
int fun_search(char ar[], int strt, int end, char value)
{
int i;
for (i = strt; i <= end; i++)
{
if (ar[i] == value)
return i;
}
}
node* contrBT(char in[], char pre[], int inStrt, int inEnd)
{
static int preIndex = 0;
if (inStrt > inEnd)
return NULL;
node* tNode = newNode(pre[preIndex++]);
if (inStrt == inEnd)
return tNode;
int inIndex=fun_search(in, inStrt, inEnd, tNode->data);
tNode->left = contrBT(in, pre, inStrt, inIndex - 1);
tNode->right = contrBT(in, pre, inIndex + 1, inEnd);
return tNode;
}
void disInorder(node* node)
{
if(node == NULL)
return;
disInorder(node->left);
cout << node->data << " ";
disInorder(node->right);
}
int main()
{
char inorder[] = {'D', 'B', 'E', 'A', 'F', 'C'};
char preorder[] = {'A', 'B', 'D', 'E', 'C', 'F'};
int len = sizeof(inorder)/sizeof(inorder[0]);
node* root = contrBT(inorder, preorder, 0, len - 1);
cout << "Created binary tree in Inorder Traversal: \n";
disInorder(root);
}
Output:
Created binary tree in Inorder Traversal:
D B E A F CComplexity Analysis
Time Complexity: O(N2)
Explanation: In the worst case, the constructed binary tree would skew leftwards. Then the root element would be the rightmost in the Inorder traversal sequence, and the search function would take the longest time.
Space Complexity: O(N)
Explanation: In this approach, the space needed depends on the size of the arrays initialized.
84+ registered