You are given a binary tree T = (V, E) (in adjacency list format), along with a designated root node r ϵ 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?

Answer rating: 100% (QA)

Do a DFS on the tree starting from r and store the ... View the full answer