# Construct tree from Ancestor Matrix

Construct tree from Ancestor Matrix « GeeksforGeeks

http://geeksforgeeks.org/forum/topic/construct-tree-from-ancestor-matrix

You are given a matrix M[n, n] for a tree with n nodes. In the given matrix M, M[i, j] is true iff node j is an ancestor of node i. Construct the tree from the given matrix.

For example, you are given below matrix.

    1  2  3  4

1  0  1  1  0

2  0  0  1  0

3  0  0  0  0

4  0  1  1  0

You need to construct the below tree. In the constructed tree ancestor relationship should be correct. A node can come on left or right of its parent as you cannot determine this information from the ancestor matrix

Node numbers used in matrix are in bracket

                   5(3)

                  /

                /

          10(2)

         /    \

       /        \

 12(1)    13(4)

This question was asked in Amazon.

'Algo:

1) Select row with all entries zero and make it as root.

2)From all entries in matrix subtract 1 if its ancestor is that root.

3) Now again search for the rows with all entries zero but dun select again the same row. You can mark all entries of that row as -1 if you have already selected that row.

4)Continue till all rows become zero.'

--

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥