Draw Binary Tree From Inorder and Postorder
Introduction
Binary Trees has been a favourite topic of many companies, including Amazon, Google, Microsoft, etc. Usually, the problems on Binary Trees look very complicated, but when we look at its solution, it seems very elegant and easy to solve.
Why is that so? This is because the topic binary trees require a stronghold over recursion and some visualization.
To help you solve binary tree problems, we will discuss a common problem, i.e., Construct a Binary Tree from a given Postorder and Inorder traversal. This problem has been asked in many interviews and tests your thought process about approaching binary tree problems.
Let's look at the problem first.
We are given 2 sequences of size N, i.e., the number of nodes in the binary tree. The first sequence is the post-order traversal of the binary tree and the second sequence is the in-order traversal of the binary tree. Your task is to construct a binary tree out of the given traversals. Return the reference or the pointer to the root of the binary tree.
Post-order Sequence :4 5 2 6 3 1
In-order Sequence : 4 2 5 1 6 3
Output Binary Tree:
Return the pointer or reference to the root containing the value 1.
Approach
Let's understand how we got to the output binary tree before jumping to the approach.
Post-order Sequence :4 5 2 6 3 1
In-order Sequence : 4 2 5 1 6 3
Now, we know that a post-order sequence can be recursively defined as:
{Elements of left subtree, Elements of right subtree, Root}
and, an in-order sequence can be recursively defined as:
{Elements of left subtree, Root, Elements of right subtree}
So using the above postorder definition, we can find the root first, the last element in the sequence. Hence root is 1.
If 1 is the root of the binary tree, then using the in-order definition, elements to the left will be present in the left subtree, and elements to the right will be present in the right subtree with root as 1, respectively.
So we can understand the above explanation using the following illustration:
Now, if we try to use the postorder and in-order recursive definitions and apply on the left and right subtrees in the above illustration, we can understand the following process using the illustration below:
So we have reached the condition that each subtree now has at most a single element. Hence we can replace the subtrees as nodes with values of each subtree.
I hope you got the essence of the question from the above example. If not, then no worries, we will discuss the approach here.
If you look, how we Construct a Binary Tree from a given postorder and Inorder traversal, you will get a sense of how the binary tree is constructed using the traversal sequences given to us.
If one tries to observe, the first thing we have done is finding the root first. After finding the root, we can now split the traversals into 3 parts, the left subtree, the root, and the right subtree, respectively.
We recursively follow the same procedure, i.e., finding root nodes of respective subtrees, splitting into 3 parts further, and repeating the same process.
Now when should we terminate? We terminate when we are left with 0 or, at most, a single element in each subtree.
We have understood how we identify repetitive work, asking recursion to do the same for us and finally returning the reference to the root.
Soapproach can be formulated as:
- Find the root node using the postorder traversal.
- Find the left subtrees and the right subtrees using in-order traversal by finding the index of the root node of respective subtrees.
- Once the root node is found, we can recurse down on the right and left subtrees, i.e., right subarray and left subarray split at respective root index to repeat the same process until we find at most a single element in either sub-array.
PseudoCode
#Assume there is a function findIndex(inOrder, val) that computes sum of i*arr[i].
Algorithm
___________________________________________________________________
procedure constructBinaryTree(inOrder, postOrder, startIndex, endIndex,postIndex):
___________________________________________________________________
1.if startIndex> endIndexor postIndex<0do # base case
2. returnNIL
3.end if
4.rootIndex ← findIndex(inOrder, postOrder[postIndex--])#find subtree root
5. root ← new Node(inOrder[rootIndex])# create the root Node
6.root.right ←constructBinaryTree(inOrder, postorder, rootIndex+1, endIndex, postIndex) # recursively create the right subtree
7.root.left ←constructBinaryTree(inOrder, postorder, startIndex, rootIndex-1, postIndex)# recursively create the left subtree
8.return root # root
9. end procedure
___________________________________________________________________
Explanation of the PseudoCode
The first condition handles the terminating conditions of the recursive functions, i.e., if we don't have any element in the subtree.
Then, we found the root index using the postorder for finding the value of the next root of the subtree. We maintain the postIndex pointer to keep track of the element we are currently at and decrement it to find the root of the subsequent subtrees.
Now similarly, we do the same for creating the right subtree.
NOTE: The startIndex and the endIndex are maintained to split the inorder array, and we can get to know elements in the sub-array that will be present in the left subtree and the right subtree, respectively. The postIndex is decremented because nodes of subtrees occur at the end.
IMPORTANT OBSERVATION
We also have a similar question in which we are given the preorder traversal sequence instead of the postOrder traversal. Note we used to recurse by creating the left subtree and then the right subtree. See Here.
So how is this different from the question in which we have the pre-order traversal?
The basic difference lies in the definition of the two traversals. The root for each subtree comes at the left-hand side of the pre-order traversal sequence and the right-hand side of the post-order traversal sequence. So while constructing the binary tree, we must take care that we build the right subtree first and then the left subtree when we are constructing the binary tree using the post-order sequence and vice versa in the case of preorder traversal sequence.
CODE IN C++
//C++ program to create the binary tree from the inOrder and postOrder traversals
#include <bits/stdc++.h>
using namespace std;
// struct Node to create Nodes in the Binary tree
struct Node
{
int data; // value of the node
Node *left; // left child
Node *right; // right child
Node(int d)
{
this->data = d;
this->left = nullptr;
this->right = nullptr;
}
};
// function that finds the index of the given value in the inOrderTraversal
int findIndex(int inOrder[], int val, int size)
{
int index = -1;
for (int i = 0; i < size; ++i)
{
if (inOrder[i] == val)
return index = i; // return index if the element matches the given value
}
return index;
}
// function to constructBinaryTree from inOrder and postOrder Traversals
Node *constructBinaryTree(int inOrder[], int postOrder[], int startIndex, int endIndex, int *postIndex, int size)
{
if (startIndex > endIndex or (*postIndex) < 0) // base case
return nullptr;
int rootIndex = findIndex(inOrder, postOrder[*postIndex], size); // subtree root Index
Node *root = new Node(inOrder[rootIndex]); // create the subtree root Node
*postIndex = *postIndex - 1; // decrement the postIndex pointer maintained
// construct right subtree
root->right = constructBinaryTree(inOrder, postOrder, rootIndex + 1, endIndex, postIndex, size);
// construct left subtree
root->left = constructBinaryTree(inOrder, postOrder, startIndex, rootIndex - 1, postIndex, size);
// return the root of the subtree.
return root;
}
// function implementing the inOrderTraversal
void inOrderTraversal(Node *root)
{
if (root == nullptr)
return; // return if there is node
inOrderTraversal(root->left); // recursively go to left subtree
cout << root->data << " "; // print the root Node of each subtree
inOrderTraversal(root->right); // recursively go to right subtree
}
int main()
{
int size = 6; // size of the array
int inOrder[] = {4, 2, 5, 1, 6, 3}; // inOrderTraversal sequence
int postOrder[] = {4, 5, 2, 6, 3, 1}; // postOrderTraversal sequence
int postIndex = size - 1; // pre order traversal index to keep track of subtree root nodes
//root Node of constructed binary tree
Node *root = constructBinaryTree(inOrder, postOrder, 0, size - 1, &postIndex, size);
//check if the inorder traversal matches with the given traversal
cout << "The inOrderTraversal of the binary tree is: ";
inOrderTraversal(root);
return 0;
}
Output
The inOrderTraversal of the binary tree is: 4 2 5 1 6 3
Time Complexity: O(n2) because we traverse the inOrder array again in each iteration for creating the root node of a subtree, which takes O(n) time. For n nodes will take O(n2) to create the whole binary tree using the above algorithm.
Space complexity: O(n), as we are recursively building up the binary tree.
Finding indices in the whole inOrder array is the main culprit for our time consumption. So can we come up with some efficient approach that does the same work in less time? Let's discuss how we can optimize the solution for the problem.
Approach to a Time-efficient Solution
If we can find the indices in O(1) time, then we can surely improve the efficiency of the algorithm from O(n2) to O(n).
So what can we use when we talk about accessing elements O(1) time. We can think of arrays or some precomputation or maps that store the elements and give O(1) access time.
We see that arrays take O(n) time, and it is not working out here. If we think about precomputation and storing results in maps, it seems to be a good idea. So if we hash the indices using the element values, we can access them in O(1) time.
Hence, we must modify the findIndex function in the above-given algorithm and store the element's indices in a map.
CODE IN C++(Time Optimized)
//C++ program to create the binary tree from the inOrder and postOrder traversals
#include <bits/stdc++.h>
using namespace std;
// struct Node to create Nodes in the Binary tree
struct Node
{
int data; // value of the node
Node *left; // left child
Node *right; // right child
Node(int d)
{
this->data = d;
this->left = nullptr;
this->right = nullptr;
}
};
// map to store the indices of elements
unordered_map<int, int> mp;
// function that finds the index of the given value in the inOrderTraversal
int findIndex(int val)
{
return mp[val]; // return the index of the given data
}
// function to constructBinaryTree from inOrder and postOrder Traversals
Node *constructBinaryTree(int inOrder[], int postOrder[], int startIndex, int endIndex, int *postIndex, int size)
{
if (startIndex > endIndex or (*postIndex) < 0) // base case
return nullptr;
int rootIndex = findIndex(postOrder[*postIndex]); // subtree root Index
Node *root = new Node(inOrder[rootIndex]); // create the subtree root Node
*postIndex = *postIndex - 1; // decrement the postIndex pointer maintained
// construct right subtree
root->right = constructBinaryTree(inOrder, postOrder, rootIndex + 1, endIndex, postIndex, size);
// construct left subtree
root->left = constructBinaryTree(inOrder, postOrder, startIndex, rootIndex - 1, postIndex, size);
// return the root of the subtree.
return root;
}
// function implementing the inOrderTraversal
void inOrderTraversal(Node *root)
{
if (root == nullptr)
return; // return if there is node
inOrderTraversal(root->left); // recursively go to left subtree
cout << root->data << " "; // print the root Node of each subtree
inOrderTraversal(root->right); // recursively go to right subtree
}
int main()
{
int size = 6; // size of the array
int inOrder[] = {4, 2, 5, 1, 6, 3}; // inOrderTraversal sequence
int postOrder[] = {4, 5, 2, 6, 3, 1}; // postOrderTraversal sequence
int postIndex = size - 1; // pre order traversal index to keep track of subtree root nodes
for (int i = 0; i < size; ++i) //store the indices of elements in the map
mp[inOrder[i]] = i;
//root Node of constructed binary tree
Node *root = constructBinaryTree(inOrder, postOrder, 0, size - 1, &postIndex, size);
//check if the inorder traversal matches with the given traversal
cout << "The inOrderTraversal of the binary tree is: ";
inOrderTraversal(root);
return 0;
}
Output
The inOrderTraversal of the binary tree is: 4 2 5 1 6 3
Time Complexity: O(n) on average because we build the binary tree by finding the index value now in O(1) time on average. The only time taken is to build the tree recursively. Hence the time complexity is O(n).
Space complexity: O(n), as a recursive stack, builds the whole binary tree and the space consumed in maintaining a map.
Frequently Asked Questions
How can we find the left view of a binary tree?
Answer) If you followed this blog, you would get to know how we can traverse a binary tree. If we want to find the left view of a binary tree, we will go to the left whenever possible, but when no node is present, the only possibility will be that the right node is visible. Hence using this approach, we can solve this problem.
What is the worst-case Time complexity if we want to search in a binary tree?
Answer)So the worst case in a binary tree would be when it is skewed, and in that case, we have the worst-case time complexity, i.e. O(n), where n is the number of nodes in the binary tree.
How can we find the level order traversal?
Answer)The level order traversal is a basic algorithm used extensively in various tree problems, which uses a queue and adds the nodes present at each level. In the case of a binary tree, we will add the children of all the nodes present in the queue and visit the nodes present in it. Also, pop the nodes once visited.
Key Takeaways
This article taught us how to Construct a Binary Tree from a given postorder and Inorder traversal by approaching the problem using a brute force approach to the most optimal approach finally. We discussed their implementation using a recursive method using illustrations, pseudocode, and then proper code.
We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out the recursive pattern followed in most binary tree problems, which simplifies the results to a greater extent.
Now, we recommend you practice problem sets based on binary trees to master your fundamentals. You can get a wide range of questions similar to the problem Construct a Binary Tree from a given postorder and Inorder traversal on CodeStudio .
Previous Article
Height of a Binary Tree
Construct a Binary Tree from a given Preorder and Inorder traversal
hoseytheitheave1946.blogspot.com
Source: https://www.codingninjas.com/codestudio/library/construct-a-binary-tree-from-a-given-postorder-and-inorder-traversal
0 Response to "Draw Binary Tree From Inorder and Postorder"
Publicar un comentario