Let T be a rooted tree with n nodes and, hence, n 1 edges. The ancestors of a le

Question

Let T be a rooted tree with n nodes and, hence, n 1 edges. The ancestors of a leaf v of T are all of the nodes on the path from v up to the root of T. Given two leaves u and v, a common ancestor of u and v is any node that is an ancestor of both u and v. The depth of a node x in T is the number of edges on the path from x to the root of T. The lowest common ancestor of two nodes u and v is the node that is an ancestor of both u and v and is the deepest such node; it is denoted LCA(u, v). As we discussed in class, we can do a DFS of T and assign pre and post numbers to each node, in O(n) time. After doing that, we will be given a pair of leaves u, v and want to find the LCA(u, v). a) Assuming that the pre and post numbers have been assigned, explain how, given a pair of leaves u, v, we can use the values pre(v), post(v), pre(u), post(u), to determine if u is an ancestor of v in a constant number of operations. This is essentially the same as problem 3.18 in the book. b) Explain how, given a pair of leaves u, v we can find LCA(u, v) in time proportional to the longest path from u or v to the LCA(u, v). c) Explain how to find the depth of each node in T in O(n) total time during the initial DFS of T. Explain how, given two leaves u and v, we can determine which of them has the shortest path to the LCA(u, v). d) Assuming the pre and post numbers have been assigned, and the depth of each node has been determined, explain how, given two leaves u, v, to find LCA(u, v) in time proportional to the shortest path from u or v to the LCA(u, v).

Explanation / Answer

During preprocessing we utilize the explore method in depth-first search to obtain the pre and post values for all the vertices in the tree. • With the pre and post values of all the vertices in the tree, we can answer the question “is u an ancestor of v” by checking whether (i) the pre value of v is greater than the pre value of u, (ii) the post value of v is less than the post value of u. (b) Pseudocode: procedure explore(G, v) visited(v) = true clock = 0 previsit(v) for each edge (v, u) E: if not visited(u): explore(u) postvisit(v) procedure previsit(v) pre[v] = clock clock = clock+1 procedure postvisit(v) post[v] = clock clock = clock+1 procedure preprocess(T, r) explore(T, r) procedure isAncestor(u, v) if pre[u] < pre[v] and post[v] < post[u] return true else return false

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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