CareerCup

we must get (0,K) for each index value.

@Manohar you are right but can we also rotate the tree upside down(by 180degrees instead of flipping the tree) and then try to join them? If yes then in that case we will have to try to find sum of both the arrays as mentioned by you front-> end + front -> end AND front->end+end->front as they could be joined in 2 ways

.....            3
     1                 2
7     12

              +

.........       5
        43             77
11       13    

Merged
             3
    1                 2
7     12       11     13
    77            43
              5


OR



...             3
    1                 2
7     12

              +

...                    5
           77               43
                        11       13    

Merged
             3
    1                 2
7     12       11     13
    77            43
              5

and both should be valid answers

The method to store coordinates in each leaf recursively, and extracting them in two arrays is definitely the right way. How ever we need to confim if the trees have to be joined with/without rotation. If the trees have to be joined after rotationg one of them by 180 degrees, then sum of y coordinates of all pairs of leaves is 0. But sum of x coordinates need not be zero, example, We can join a tree of height 2 with a tree of height 100 if they have the same number of leaves properly aligned. So what we should check is that the distance of the leftmost leaf to each other leaf should be the same in both the trees, heres some code, Call assignCoord(root, 0, 0);

void assignCoord (node root, int x, int y) {
	if(root == null)
		return;
	root.x = x;
	root.y = y;
	assignCoord(root.left, x-1, y+1);
	assignCoord(root.right, x+1, y+1);
}

Class Coord {
	int x;
	int y;
	public Cord(int a, int b) { x = a; y = b}
}

ArrayList<Coord> list1 = new ArrayList<Coord> ();
ArrayList<Coord> list2 = new ArrayList<Coord> ();

call addLeaf(root, list1) and addLeaf(root, list2)

void addLeaf (node root, ArrayList<Coord> l) {
if(root == null)
return;
if(root.left == null && root.right == null) {
Coord temp = new Coord(root.x, root.y);
l.add(temp);
addLeaf(root.left, l);
addLeaf(root.right, l);
}

//pseudocode
Boolean check (ArrayList<Coord> l1, ArrayList<Coord> l2) {
	if (l1.size() != l2.size())
		return false;
	//traverse l1 from left to right and l2 from right to left
	//sum of y should be constant;
	//distance of leftmost leaf in l1 to all other leaves in l1, should be the same as dist of rightmost leaf in l2 to all other leaves in l2
	
}

*correction, sum of Y coords must be constant and not zero

there are 2 conditions

......2
...../.\
....1...2

......+

......3
...../.\
....1...2
	
......=
	
......2
...../.\
....1...2
.....\./
......3

these both can be merged

what of

......2
...../.\
....1...2
.../.\
..2...3

......+
	
......3
...../|\
....2.3.2
	
......=
	
.....?

can these be merged?

please don't say tree should be binary, as this is just for explanation

I think you are write cyrus, we have to check weather both tree have equal number of leaf nodes or not ?

so
......2
...../.\
....1...2
.../.\
..2...3



......+

......3
...../|\
....2.3.2

......= 2
........./..\
.......1....2
...../...\.....\
..2......3....\
..|.......|......|
..2.....3.....2
...\......|...../
.....\....|.../
.......\..|../
.........\|/
.........3

this is how they can be merged
so we just have to check leaf node, lets one tree have M number of nodes and other have N number of nodes, so the this require Omega(N+M) time complexity

Isn't it like checking if two trees are mirror images or not (not in terms of values, only structure)? This should also take care of the height of the leaves.

@learner here we only need to check leaves. Not the whole tree, mirror image will consider whole tree.

@Bin, store leaves of first tree in queue and second tree in stack and then parallely keep popping from both and comparing for equality.