Home > Uncategorized > ancestor reporting in a tree

ancestor reporting in a tree

S Dasgupta- 3.18 :You are given a binary tree T = (V;E) (in adjacency list format), along with a designated root  node r belongs to V . Recall that u is said to be an ancestor of v in the rooted tree, if the path from r to v in T passes through u. You wish to preprocess the tree so that queries of the form “is u an ancestor of v?” can be answered in constant time. The preprocessing itself should take linear time. How can this be done?

Solution:

Let Ancestor[n][n] be an two dimentional array. If there is a query “is u an ancestor of v” our program will answer “yes” if A[u][v] is true otherwise it will report “no”.

Algorithm:

DFS-visit ( u , list){

Process_ancestor();

time = time + 1

u.color = GRAY;

foreach v belongs to adj[u] {

append(list,v);

DFS-visit (v,list);

remove_last_element(); // which will remove v from the end of the list.

}

}

Process_parent ( list ) {

if ( list.size > 1 ) {

for ( i=1; i<=list.size; i++) {

for ( j=i+1; j<=list.size; j++)

ancestor[list[i]][list[j]] = true; // list[i] is a ancestor of list[j]

}

}

}

Process_query( u,v) {   // This will answer our question.

if ( ancestor[u][v] == true ) return yes;

return false;

}

Advertisements
  1. D
    February 15, 2013 at 10:31 pm

    Initializing an n by n array takes n^2 time, so the preprocessing is not linear.

  1. No trackbacks yet.

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

%d bloggers like this: