You are given a binary tree T = (V, E) (in adjacency list format), along with...

  

Transcribed Image Text:

You are given a binary tree T = (V, E) (in adjacency list format), along with a designated root node re 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 pre-process the tree so that queries of the form "is u an ancestor of v?" can be answered in constant time. The pre-processing itself should take linear time. How can this be done? SO You are given a binary tree T = (V, E) (in adjacency list format), along with a designated root node re 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 pre-process the tree so that queries of the form "is u an ancestor of v?" can be answered in constant time. The pre-processing itself should take linear time. How can this be done? SO

Answer rating: 100% (QA)

Solution Let Ancestornn be an two dimentional array If there is a query is u an ancesto... View the full answer