CODEWITHSUNDEEP
algorithmdata-structurestreelongest-path
user2129227
user2129227

Reputation: 97

Find longest path between set of nodes in a tree

Recently came across a programming question.

Given a tree, can be non-binary, can be a single chain (or linear), with N nodes.

Input will be a set of K nodes, denoted a1,a2....ak. I'd like to find the longest simple path(s) that start from one of those K nodes and finish at one of those K nodes (different from start nodes). A logarithmic algorithm depending on N or K should meet the running time requirements (eg: KlogK, KlogN) if needed should be within my desired time limit.

Thank you

Upvotes: 1

Views: 1775

Answers (1)

Srikar Appalaraju
Srikar Appalaraju

Reputation: 73688

Maybe you can try this approach -

  1. Run DFS from any node to find the farthest leaf node, lets call it node X.
  2. Run another DFS to find the farthest node from X.
  3. The path you found in step 2 is the longest path in the tree.

This should work for all trees, not just binary trees.

Upvotes: 3

Related Questions