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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s