ekapil2
BAN USERPrashant's answer is best here I guess. But, let me give my two cents.
Call matrix by matrix(root, new ArrayList<BinaryTree());
I am just print the nodes, you can use a matrix in case you life.
private static void matrix(BinaryTree root, ArrayList<BinaryTree> list){
if(root == null){
return;
}
list.add(root);
matrix(root.left, list);
matrix(root.right, list);
list.remove(list.size()-1);
System.out.println();
for(int i = 0 ; i < list.size();i++){
BinaryTree parent = list.get(i);
System.out.print("[" + parent.data + "->" + root.data + "]");
}
}
this is somewhat closer to the solution. I am not sure if its correct.
So, we can do like this.
Maintain the maximum depth of left and right sub tree at each node. Is it correct that the final answer is the node which has max of value for left and right max values.
Why to run Floyd Warshal?
Your idea is correct, make a graph of the binary tree.(un- directional graph and an edge exists between a and b in case a is parent of b or b is a parent of a.)
Now run BFS making a counter on numbers of levels travelled. when it reaches k, exit. The tree formed with BFS are the nodes with k distance from the node.
I don't think in case that possible. The problem is related to Transitive closure, where a path of length K exists by OR Adj_1 || Adj_2 || .....|| Adj_k.
where Adj_1(i,j) = 1 in case i, j path exists 0 other wise.
And Ajd_2 = matrix multiplication of Adj_1 with itself .
Since order and occurrences of elements doesn't match make a bit map vector of each array where bit_x i = 1 in case the element is present. The array would match if bit_x XOR bit_y == 1. (All present or not present).
This won't be efficient in case one element is 1 and other is 10000. But, this can be one solution.
The count is nothing but called conversion is an array. Consider them the number of pairs which needs to be swapped to make the array sorted. There is a modified version of merge sort to do this in O (nlogn) time.Its one of the back problem of Cormen. We did it in our algo class.
- ekapil2 November 07, 2010For any Rectangle find its four corresponding lines using y-y1/(x-x1) = y2-y1/x2-x1
You got four lines for Rectangle A.
You got four points for rectangle B.
For A or B to intersect ( I am assuming this is what overlap means), the value of one point should be > 0 and < 0 for two parallel lines and < 0 and > 0 for the other two parallels lines. ( or the other way around)
In case not they would have the same sign. ( both > 0 and both < 0 or other way around).
A graph which doesn't has a cycle is not necessarily a TREE!
- ekapil2 November 16, 2010