riyu
BAN USERDear Tulley,
Running the modified algo on the same example with little change
1
/ \
2 3
/
4
/
5
After sorting
1 2 3 4 5
1 0 1 1 1 1
2 0 0 0 1 1
4 0 0 0 0 1 <- not 3 its 4
3 0 0 0 0 0
5 0 0 0 0 0
Notice that I have removed the child on 3 from the previous example I posted, just to make it simple.
I am assuming that you meant AncestorMatrix[K][J]==1 instead of AncestorMatrix[I][J]==1 inside the K loop
I = 1 -> node 1 (0 1 1 1 1)
0 1 1 1 1
R = 1
out of j = 2 3 4 5 which have A[i][j] = 1 only 2 & 3 will escape the continue...so we have
1
/ \
2 3 queue = 2 3
I = 2 -> node 2 (0 0 0 1 1)
queue = 2 3
R = 2
out of j = 4 5 which have A[i][j] = 1 only 4 will escape the continue...so we havee
1
/ \
2 3 queue = 3 4
/
4
I = 3 -> "node 4" (0 0 0 0 1)
queue = 3 4
R = 3
only j = 5 has A[i][j] = 1 and it will escape the continue...so we have
1
/ \
2 3 queue = 4 5
/ \
4 5
1) we are not going to modify 3 after this so we will end up with this tree...which is not the same as the original.
2)you introduced another 'for' loop, so in the worst case your algo will run O(n^3). I have not verified this fact but i think the worst case will be when all nodes have only left child or only right child
-> What you can try is instead of building the tree top to bottom in your 2 loop algo (the one before this one), you can try bottom up.
-> Or you might want to consider sorting the array column wise based on the number of 1s and arranging the rows to match the column order. then see the problem from the column perspective instead of row..
Generally it is desirable to have the input array unmodified. So when you sort you are not actually sorting the array, instead have an auxillary array that will hold the indices in sorted.
Hi Tulley,
Running your algo for this case is not working. Check if this is what you meant
1
/ \
2 3
/ \
5 4
/
6
After sorting the array, it will look like this
1 2 3 4 5 6
1 0 1 1 1 1 1
2 0 0 0 0 1 1
3 0 0 0 1 0 0
5 0 0 0 0 1 0
4 0 0 0 0 0 0
6 0 0 0 0 0 0
I = 1
queue = Root
isLeftChild = false
XOR of
0 1 1 1 1 1
0 0 0 0 1 1
will give
0 1 1 1 0 0
Left will be 2
Right will 3 then will be changed to 4
so we have
1
/ \
2 4
This is not same as what we started with and as we are not modifying the root again root's children are not going to change
- riyu April 10, 2011
hey anonymous,
The row corresponding to 3 is not containing any "1" true....but because we sorted the matrix, the matrix is going to look like this.
So when "R" is node 3(which we got from the queue)..it is not guaranteed to inspect the row corresponding to 3, as in this case where we are inspecting node 4's row even though "R" is 3 and I = 3
And for your second statement. K loop will run from "K = I + 1 to max-row - 1" that is "K = 3+1 to 5-1" or "K = 4 to 4". So for J = 1,2,3,4,5 we are checking if A[4][J] is 1, if it is then we skip. From the above matrix we can see that there are no 1s anywhere in the row 4 (that is node 3's row). So R->left = newNode() is executed and I am assuming Tulley is setting the value somewhere there.
- riyu April 11, 2011