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 :

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


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

Note the tree looked like :

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

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

Recommended Answers

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
using namespace std;
void printBFS(int arr[], int size);

int main()
	int arr[100];
	int size;
	cout<<"Enter number of nodes";
	cout<<"Enter inorder traversal";
	for(int i=0;i<size;i++)
	return 0;

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

	//Find the depth of tree
	while(j != 1)

	//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++)

		while(i < size+1)
			if(arr[i-1] != -1)
				cout<<arr[i-1]<<" ";
			arr[i-1] = -1;

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.