Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
@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
}
I think the rightmost leaf of a tree should be equal to the leftmost tree of the other.
Insert all the leaf nodes of 1 tree in an array
Insert all the leaf nodes of second tree in another array
Now reverse 1 array and compare..they should be same
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.
1. go through the first tree and find all leaves, store them
2. go through the second tree and compare each leaf with pre-stored leaves
space O(n), time O(n^2)
or we can do it in o(n) if each node has parent pointer. one leaf can only pointer to one parent which ether in tree1 or tree2. so we can iterate two tree by storing parent(pptr) and current node pointer(nptr), check pptr with nptr->parent if nptr is leaf.
A very easy way is to traverse each tree from top to bottom and assign a coordinates value (X,Y) to each node.. assign root node as (0,0). If a node has coordinates (x,y) then its left child is (x-1,y+1) and right child is (x+1,y+1).
- Manohar Singh January 21, 2013After assigning values to each node for both of the trees, Collect coordinates values of the leaf node in two separate array. If size of two arrays are not same then its not possible to join the two trees. Otherwise try to sum up two arrays starting both from start index or one array from the end. If it is possible to get pair value (0,K) , K is some constant; then we can join the two trees , otherwise it is not possible.