CODEWITHSUNDEEP
algorithmtreepath-finding
luka25
luka25

Reputation: 33

Shared Path in a Tree

I have a tree and 3 nodes A,B,C.The problem is to find the size of a path that A and B will share on their shortest paths to C.

There are 3 cases:

  1. When C is an ancestor of A and B. In this case the answer is min(depth(A), depth(B)) - depth(C)

  2. When C is an ancestor of A but not B or vice versus. In this case, the answer is 1, just node C

  3. This is a case I can't figure out when neither of A and B is a descendant of C.

I'll have many queries so I need an efficient way. Disregarding that we can get every LCA in O(logN), every query should be O(1).

Upvotes: 2

Views: 115

Answers (2)

DAle
DAle

Reputation: 9117

Algorithm with tree modification

The simplest algorithm I could come up with may need a modification of the source tree depending on its initial representation.

  1. We need to make C the root of the tree. So we need to change parent-child relationships within the tree.

  2. Find the lowest common ancestor (LCA) of A and B. LCA is the node with maximal depth that is the ancestor of both A and B (and LCA(A, A) = A).

  3. The answer is depth(LCA(A,B)).

Algorithm without tree modification

If we cannot transform the tree then:

  1. If C is the ancestor of both A and B then the answer is depth(LCA(A, B)) - depth(C) + 1. (You have a mistake in the question.)
    enter image description here

  2. If C is the ancestor of A and not B then the answer is 1. (and vice versa) enter image description here

  3. If C is the descendant of A and not B then answer is depth(C) - depth(A) + 1. (and vice versa)
    enter image description here

  4. If C is the descendant of both A and B then answer is depth(C) - max(depth(A), depth(B)) + 1.
    enter image description here

  5. If C is not ancestor or descendant of A and B the answer would be distance between C and vertex D = LCA(A, B) that would be equal to depth(C) + depth(D) - 2*depth(LCA(C, D)) + 1.
    enter image description here

Update: now there is an O(1) per operation requirement appeared in the question. I think that only thing you can do to guarantee O(1) time complexity is to precompute all LCA(i, j). This can be done, for example, with Tarjan's off-line LCA algorithm.

Upvotes: 0

CodeHunter
CodeHunter

Reputation: 2082

As DAle pointed out in the above answer, one approach can be based on the way he tells, i.e. by making the root of tree as C and then checking for path.

Another approach can be to find, in a similar way, Lowest Common Descendant (LCD) of both A and B. In short, we can find the first node where the path of both A and B would intersect while going towards C and then give the size of the path from that node to C. There can be few cases then:

  1. LCD of A and B (going towards C) is A: return length of path from A to C
  2. LCD of A and B (going towards C) is B: return length of path from B to C
  3. LCD of A and B (going towards C) is C: return 0
  4. LCD of A and B (going towards C) is a node D: return length of path from D to C

Upvotes: 2

Related Questions