DAA: Construct a Tree from Inorder and Preorder Traversals
Construct a Tree from Inorder and Preorder Traversals
We are given inorder and preorder traversals of a tree. We need to generate a tree from these traversals.
Example:
Inorder[] = { 3, 1, 4, 0, 5, 2 }
Preorder[] = { 0, 1, 3, 4, 2, 5 }
Output - 3 1 4 0 5 2
The tree constructed for the output is:
Let us understand how the tree is formed.
- In Preorder traversal, the first node is the root node, and in Inorder traversal, the root node is somewhere between the array.
- Once we find the root node 0, we look that that particular node in the inorder traversals.
- The node to the left of the root will come in the left subtree, and the right to the root will come in the right subtree.
- We will similarly repeat this process until the whole tree is generated.
In preordering, we get 1, so we search for it in preorder, and the nodes left to 1 will come in the left subtree, and nodes to the right will come in the right subtree.
Now the left subtree is formed. Then we get 2 in the preorder traversal. We look for it in the inorder traversal. The value to the left will become the left subtree of 2, and the value to the right will become the right subtree. We get only 5. So it becomes the left subtree, and hence the whole tree is generated.
Approach 1
- Take values starting from the beginning in preorder. Increment the indexes to get another value in the recursive call.
- For the picked element, create a new node and insert the value.
- Find the picked element in our inorder array and call recursively for the left subtree and right subtrees.
- Return root node.
C++ Code:
#include <bits/stdc++.h>
using namespace std;
// Create Node structure
class node {
public:
int data; // The data to node
node* left; // The left pointer to node
node* right; // The right pointer to node
};
// Function Prototypes
int search(int arr[], int strt, int end, int value); // To search the value in Inorder Array
node* newNode(int data); // Allocate memory to new node
node* newNode(int data) // Create a new node
{
node* Node = new node();
Node->data = data; // Assign value
Node->left = NULL; // left point to NULL
Node->right = NULL; // right point to NULL
return (Node);
}
node* buildTree(int in[], int pre[], int inStrt, int inEnd) // The function is called recursively
{
static int preIndex = 0; // This index increment and take the value of Preorder array
if (inStrt > inEnd) // If we go out of bound
return NULL;
node* tNode = newNode(pre[preIndex++]); // Allocate memory to new created tree
if (inStrt == inEnd) // No children in this node
return tNode;
int inIndex = search(in, inStrt, inEnd, tNode->data); // Find index in inorder traversa;
tNode->left = buildTree(in, pre, inStrt, inIndex - 1); // Build left subtree
tNode->right = buildTree(in, pre, inIndex + 1, inEnd); // Build right subtree
return tNode;
}
// Linear Search to find node in Inorder array
int search(int arr[], int strt, int end, int value)
{
int i;
for (i = strt; i <= end; i++) {
if (arr[i] == value)
return i; // return index of found element
}
}
void printInorder(node* node) // Print the inorder of generated tree
{
if (node == NULL) // If we reach leaf node
return;
printInorder(node->left); // Find left child
cout << node->data << " "; // Print root node
printInorder(node->right); // Find right child
}
// Main Function
int main()
{
int in[] = { 3, 1, 4, 0, 5, 2 };
int pre[] = { 0, 1, 3, 4, 2, 5 };
node* root = buildTree(in, pre, 0, 5); // Get the root of newly created tree
cout << "Inorder traversal of the newly constructed tree is \n";
printInorder(root); // Print the new created tree
}
Output
Inorder traversal of the newly constructed tree is 3 1 4 0 5 2
Time complexity:
O(n*n)
O(n) for building a new tree and searching the index in inorder uses linear search, so it takes O(n).
Approach 2
From the above code, it is observed that the search operation takes O(n) time extra to find the element index in inorder. It can be reduced to O(n) if we already find the inorder array indexes and store them in a data structure.
To do this task, we can use an unordered map whose key will contain the inorder element, and the index will be the index of that particular element.
C++ Code:
#include <bits/stdc++.h>
using namespace std;
// Create tree structure
struct Node {
int data; // data to node
struct Node* left; // left pointer to node
struct Node* right; // right pointer to node
Node(int x)
{ // parameterised constructor for passed x value
data = x;
left = NULL;
right = NULL;
}
};
// Function prototype
Node* buildTree(int inorder[], int preorder[], int n);
void printInorder(Node* node) // Print the inorder of generated tree
{
if (node == NULL) // If we reach leaf node
return;
printInorder(node->left); // Find left child
cout << node->data << " "; // Print root node
printInorder(node->right); // Find right child
}
int main()
{
int inorder[] = { 3, 1, 4, 0, 5, 2 };
int preorder[] = { 0, 1, 3, 4, 2, 5 };
Node* root = buildTree(inorder, preorder, 6);
cout << "Inorder traversal of the newly constructed tree is \n";
printInorder(root);
}
int idx = 0; //index to iterate in preorder
unordered_map<int, int> mp; // map to store indexes
Node* solve(int in[], int pre[], int lb, int ub)
{
if (lb > ub)
return NULL; // if we reach boundary
Node* res = new Node(pre[idx++]); // Create new node
if (lb == ub)
return res;
int mid = mp[res->data]; // find the index of preorder value in inorder
res->left = solve(in, pre, lb, mid - 1); // make left of mid as left subtree
res->right = solve(in, pre, mid + 1, ub); // make right of mid as right subtree
return res;
}
Node* buildTree(int in[], int pre[], int n)
{
idx = 0;
mp.clear();
for (int i = 0; i < n; i++) // store indexes
mp[in[i]] = i;
Node* root = solve(in, pre, 0, n - 1); // helper function to build the tree
return root;
}
Output
Inorder traversal of the newly constructed tree is 3 1 4 0 5 2
Time complexity:
O(n)