CareerCup

I would say that if one of the two arrays contains numbers in pre-order traversal, and the other in post order traversal, and if we traverse the one in preorder in forward direction and the one in post order in backward direction then we will get identical trees.

eg: A: preorder
--->

B: postorder
<-----
Result is identical binary trees. The idea of identical trees is that they should have keys in teh identical place.

I do not get the question.
What does it mean by array elements to form identical binary tree ?

I think he means to have the same number of nodes in each level for each tree.

If that is the case it is simple, just sort the arrays and choose any of them to be the root.

If the first array contains the keys in in-order and the second in pre/post-order, we are certain to rebuild the tree.

heap implementation

We can construct a binary tree: from inorder traversal + one of pre-order OR post order traversal.

It takes linear time.

I dont think the keys are required to be in any specific order in the two arrays. The question asks you to come up with those permutations and see if they can form an identical binary tree. I think as some one mentioned above if you sort the arrays and try to build a binary tree then it will tell you if they can be identical or not.

Assuming the arrays give the order of insertion ... the root element (first element of array) has to be the same. Now for all number in left subtree of root relative order has to be maintained, same for right subtree e.g. 3,4,1,5,2,7 will give same tree as 3,1,2,4,5,7 or 3,4,5,1,7,2. So if 3 is root 4,5,7 should appear in that order and similarly 1,2 in any permutation

if I have a tree:

D
  B   F
 A

I can serialize this tree 4 ways to get exact same tree back:
D B F A
D F B A
D B A F
D F B A

Hope that's enough of a hint.

I have one condition in mind. First the first element to be inserted has to be the same while forming the binary trees, call it 'c'.
Next if the two arrays have the same order of elements for elements > c and for elements < c in any order be it so, the tree formed will be same.

For ex.
Array A: 5 7 9 3 1 8
Array B: 5 3 7 1 9 8.
They both will form the same tree. as all elements > 5 ( 7,9 and 8 ) maintain the same order and same with elements less than 5.
I presume that this is a sufficient condition. Not sure if it can be called a necessary one.

Only if two arrays contain keys in exactly same order then binary trees (or even binary search tree) formed from them will be identical.

You might think fixing root node might be sufficient condition but its not as well.

Example: Array A contains : 1,2,3,4 and Array B contains: 1,3,2,4

Binary Tree from Array A taking elements from left to right is:
1
/ \
2 3
/
4

Binary Search Tree from Array B taking elements from left to right is:
1
/ \
3 2
/
4

Binary Search Tree from Array A taking elements from left to right is:
1
\
2
\
3
\
4

Binary Search Tree from Array B taking elements from left to right is:
1
\
3
/\
2 4

As you can see these two trees are not identical because the keys in the arrays are not in same order. Even in this case first element being same (which is another way of saying that same root for both trees) the trees are not identical because rest of the keys after root are not in same order in the arrays.

I guess even if we want to build balanced search tree with same algorithm (like red-black or AVL tree) the necessary condition will be the same as binary tree.

kausikghatak: i agree with your logic/conditions !