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.