Programming challenge questions: Complete Binary Tree Reconstruction

[mrnutty]

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!

[mrnutty]

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.

[vidit_X]

Can you please provide some testcases for testing?

[vidit_X]

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;
		}
	}
}

[mrnutty]

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

[vidit_X]

Did you check my code? Is it correct?

P.S : It works only for integers