Problem question: Given the sequence A and B, where A is the inorder traversal value and B is the pre-order traversal value, reconstruct the binary tree that produces such results when performing inorder and pre-order traversal on that binary tree. To reconstruct the binary tree you can simply print the breadth-first traversal of the reconstructed tree. You can assume that the size of A and B is 2n+1, that is, its a complete and full binary tree.

Example :

input:
A = 1 2 3 4 5 6 7 #in order traversal
B = 4 2 1 3 6 5 7 #pre order traversal

output:

Bredth-first tree: 4 2 6 1 3 5 7.

Note the tree looked like :

``````4
/ \
2   6
/\  /\
1 3  5 7``````

Bonus: For fast implementation in terms of speed and memory!

## All 5 Replies

No takers? Need hint?

First try to think of how you can use the information given to convert it back into a tree. Then worry about displaying it.

Can you please provide some testcases for testing?

Here's my solution, it doesn't need Pre-order traversal just the inorder traversal.

``````//Will only work if it is a complete and full binary tree
#include<iostream>
using namespace std;
void printBFS(int arr[], int size);

int main()
{
int arr[100];
int size;
cout<<"Enter number of nodes";
cin>>size;
cout<<"Enter inorder traversal";
for(int i=0;i<size;i++)
cin>>arr[i];
cout<<"\nBFS-";
printBFS(arr,size);
return 0;
}

void printBFS(int arr[], int size)
{
int i, k, x=0, j =size+1;

//Find the depth of tree
while(j != 1)
{
j=j/2;
x++;
}

//Can't explain here :P
for(j = x-1; j >=0; j--)
{
int k, x = 1;

//pow(2, j);
for(k=0; k< j; k++)
x*=2;

k=1;
i=x*k;
while(i < size+1)
{
if(arr[i-1] != -1)
cout<<arr[i-1]<<" ";
arr[i-1] = -1;
k++;
i=x*k;
}
}
}``````

Actually with the assumption of being a complete full binary tree, this problem turns out to be pretty easy. No need to reconstruct any tree at all.

Some more test cases:

in-order: 1 2 3
output: 2 1 3

in-order: 1 2 3 4 5 6 7
output: 4 2 6 1 3 5 7.

in-order: A B C D E F G
output: D B F A C E G

Did you check my code? Is it correct?

P.S : It works only for integers

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.