The inorder and levelorder traversals for a binary tree along with the total number of nodes is given in a function definition, we have to calculate the minimum height of binary tree for the given inputs.
Can we calculate without constructing the tree?
func(int[] inorder, int[] levelorder, int n)
{
// write code here
}
for example
{ 4,2,5,1,6,3,7},{1,2,3,4,5,6,7}, n=7.And expected o/p was
3
a very simple approach is to build the tree and then find it's height.
let's suppose structure of the node is : struct Node { int key; struct Node* left, *right; };
Node* **newNode**(int key)
{
Node *node = (Node *)malloc(sizeof(Node));
node->key = key;
node->left = node->right = NULL;
return (node);
}
int **getHeight**(Node* root){
if(root==NULL) return 0;
return max(getHeight(root->left)+1,getHeight(root->right)+1);
}
Node* **getNode**(Node* root,int key){
if(root!=NULL){
if(root->key == key) return root;
return getNode(root->left,key) != NULL ? getNode(root->left,key):
getNode(root->right,key);
}
}
void **buildTree**(int inorder[], int levelOrder[], int i, int j,int n)
{
Node* head = newNode(levelOrder[0]);
i++;
int comp = 0;
while(i<j){
int key = levelOrder[comp];
Node* ptr = getNode(head,key);
int k = n-1;
while(k>=0 && inorder[k]!=key) k--;
if(k>0 && inorder[k-1]!=-1){
ptr->left = newNode(levelOrder[i]);
i++;
}
if(k<n-1 && inorder[k+1]!=-1){
ptr->right = newNode(levelOrder[i]);
i++;
}
inorder[k] = -1;
comp++;
}
int height = getHeight(head);
**cout<<height<<" ";**
}
yes, you can do that without even constructing the tree.
for that use two queue.
see given below code for better understanding.
void **buildTree**(int inorder[], int levelOrder[], int i, int j,int n)
{
queue<int>q1,q2;
q1.push(levelOrder[0]);
int k = 1,height = 0;
while(!q1.empty() || !q2.empty()){
if(!q1.empty()) height++;
while(!q1.empty()){
int val = q1.front();
for(int i = 0;i<n;++i){
if(inorder[i] == val) break;
}
if(i>0 && inorder[i-1] !=-1 && k<n)
q2.push(levelOrder[k++]);
if(i<n-1 && inorder[i+1] !=-1 && k<n)
q2.push(levelOrder[k++]);
inorder[i] = -1;
q1.pop();
}
if(!q2.empty()) height++;
while(!q2.empty()){
int val = q2.front();
for(int i = 0;i<n;++i){
if(inorder[i] == val) break;
}
if(i>0 && inorder[i-1] !=-1 && k<n)
q1.push(levelOrder[k++]);
if(i<n-1 && inorder[i+1] !=-1 && k<n)
q1.push(levelOrder[k++]);
inorder[i] = -1;
q2.pop();
}
}
cout<<height<<endl;
}
Below code snippet would calculate the height of the tree without constructing it.
#include <iostream>
#include <queue>
using namespace std;
int minHeight(int inOrder[], int levelOrder[], int n)
{
int i=1;
queue<int>q1,q2;
q1.push(levelOrder[0]);
int k = 1,height = 0;
while(!q1.empty() || !q2.empty()){
if(!q1.empty()) height++;
while(!q1.empty()){
int val = q1.front();
for(int i = 0;i<n;++i){
if(inOrder[i] == val) break;
}
if(i>0 && inOrder[i-1] !=-1 && k<n)
q2.push(levelOrder[k++]);
if(i<n-1 && inOrder[i+1] !=-1 && k<n)
q2.push(levelOrder[k++]);
inOrder[i] = -1;
q1.pop();
}
if(!q2.empty()) height++;
while(!q2.empty()){
int val = q2.front();
for(int i = 0;i<n;++i){
if(inOrder[i] == val) break;
}
if(i>0 && inOrder[i-1] !=-1 && k<n)
q1.push(levelOrder[k++]);
if(i<n-1 && inOrder[i+1] !=-1 && k<n)
q1.push(levelOrder[k++]);
inOrder[i] = -1;
q2.pop();
}
}
return height;
}
int main()
{
int inOrder[] = {4,2,5,1,6,3,7}; //input1
int levelOrder[] = {1,2,3,4,5,6,7}; //input2
int n=sizeof(inOrder)/sizeof(int); ////input3
cout<<minHeight(inOrder, levelOrder, n)<<endl;
return 0;
}
Question : If the in-order and level order traversal of a tree are given, what is the minimum height of the tree
Example 1 :
input1 : {2,1,3}
input2 : {1,2,3}
input3 : 3
Output : 2
Example 2 :
input1 : {4,2,5,2,6,3,7}
input2 : {1,2,3,4,5,6,7}
input3 : 7
Output : 3
If you got this question in Campus round of Naggaro or on metti then it will a good solution for you
class Node:
def __init__(self, key):
self.data = key
self.left = None
self.right = None
def buildTree(level, ino):
if ino:
for i in range(0, len(level)):
if level[i] in ino:
node = Node(level[i])
io_index = ino.index(level[i])
break
if not ino:
return node
node.left = buildTree(level, ino[0:io_index])
node.right = buildTree(level, ino[io_index + 1:len(ino)])
return node
def height(root):
if root is None:
return 0
else:
return max(height(root.left),height(root.right))+1
#This is the function you have to write
def minHeight(input1,input2,input3):
global root
root = buildTree(input1, input2)
return height(root)
inorder = [4,2,5,1,6,3,7]
levelorder = [1,2,3,4,5,6,7]
print("height : ",minHeight(levelorder,inorder,len(inorder)))
