The ancestor matrix is defined as follows:

If there are

nnodes in the tree, then it will be a nxn matrix. An elementa[i][j]is defined as follows:

a[i][j] = 1, if nodeiis an ancestor of nodej,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.

- Find all columns that have a single

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.

Advertisements