You are given a rooted binary tree T = (V, E), along with a designated root node

Question

You are given a rooted binary tree T = (V, E), along with a designated root node r V . The size of V is n. Recall that a node in a tree keeps tracks of its descendants and its parent node. Also recall that node u is said to be an ancestor of node v in the rooted tree, if the path from r to v in T passes through u. A commonly performed querying on the trees is: given two nodes u and v, is u an ancestor of v? You wish to preprocess the tree so that queries of this form for any two nodes u and v can be answered in constant time. The preprocessing itself should take linear time. That is, you can spend O(n) time before any query arrives; then you must answer each query like “is node u an ancestor of node v?” in constant time.

Explanation / Answer

For Answer in contant time, we need to save some data at each Node while preprocesing.

Data need to save
1) Level of the Node in the tree
2) PostOrder index of the Node in the tree
3) value of the Node in the tree

our Array while preprocesing will be like this
class Node{
   int data;
   Node parent;
   Node left;
   Node right;
}

class List{
   Node n;
   int level;
   int PostOrder_index;
}

List[] l = new List[1000];

is u ancestor of v?
=> u can be ancestor of v if and only if
1) PostOrder index of u must be greater than that of v.
2) Level of the u must be less than Level of v.

boolean is_ancestor(u,v)
   if (l.get(u).level > l.get(v).level)
       if (l.get(u).PostOrder_index > l.get(v).PostOrder_index)
           return true;
       end
   end
   return false;
end

time complexity : O(1)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.