# Constructing a Tree Given Ancestor Matrix

The ancestor matrix is defined as follows:

If there are n nodes in the tree, then it will be a nxn matrix. An element a[i][j] is defined as follows:

a[i][j] = 1, if node i is an ancestor of node j,

otherwise a[i][j] = 0

Given this matrix construct the tree.

My algorithm is as follows:

• Find the zero column in the matrix –  it is the root of the tree. Lets call it node k
• Remove row k and column k from the matrix. While there are more elements in the matrix, do:
• Find all columns that have a single 1 in them.
• For each such column, associate the row index as the parent to the column index i.e. if a[n][m] is the only 1 in the column, then n is the parent of m.
• If there are no such columns, then indicate the corresponding indices as the leaves of the tree and quit.
• Remove the corresponding rows and columns from the matrix.

What is the complexity of the algorithm – the steps – finding a zero column or finding a single 1 column each is of O(n^2) complexity. So the complexity is O(n^2). But, if the ancestor matrix is represented as a sparse matrix, then the complexity of the algorithm reduces drastically – need to figure that out.

The algorithm is very crude and needs to  be refined.