1
$\begingroup$

Suppose we are given an arbitrary rooted tree. We want to find two nodes that have the maximum distance among all pairs of nodes. I am looking for an algorithm with time complexity $\mathcal{O}(n)$, where $n$ is the number of nodes in the tree. Note that there may be more than one pair of nodes that satisfy this condition, but finding any one pair is enough.

Also, I am writing code in Java, and the input format is as follows: the first line gives the number of nodes, and the next $n-1$ lines give two numbers $u_i$ and $v_i$ each, indicating that there is an edge between nodes $u_i$ and $v_i$. What would be a good data structure to store and represent the rooted tree for this problem and implement the algorithm?

Any help is greatly appreciated!

$\endgroup$

1 Answer 1

1
$\begingroup$

I don't know much about java, but there could be several ways to represent the tree:

  • an array of $n$ adjacency lists, like an undirected graph;
  • an array of $n$ integers, that contains the parent of each node (and so that the root is its own parent);
  • an inductive structure, with a node and the list of its children.

The idea of the algorithm is simple:

  • find a leaf $x$ of maximum depth;
  • find the farthest node $y$ of $x$ (either by using BFS, or by finding a leaf of maximum depth in the tree rooted in $x$).

Let $V$ be the set of nodes of the tree.

To prove that $d(x, y) = \max\limits_{u,v \in V^2}d(u, v)$, consider $u$ and $v$ two nodes that maximize $d(u, v)$, and $w$ be their lowest common ancestor and consider two cases:

  • if $w$ is an ancestor of $x$, then let $z$ be the lowest common ancestor between $u$ and $x$ (without loss of generality). Since $x$ has greater depth than $u$, then: $$d(u, v) = d(u, w) + d(w, v) \leqslant d(x, w) + d(w, v) = d(x, v)$$

    enter image description here

  • if $w$ is not an ancestor of $x$, then let $z$ be the lowest common ancestor between $w$ and $x$. Since $x$ has greater depth than $w$, then: $$d(u, v) = d(u, w) + d(w, v) \leqslant d(u, z) + d(w, v) \leqslant d(x, w) + d(w, v) = d(x, v)$$

    enter image description here

In both case, the maximum distance can be reach with $x$ as one of the two nodes, which proves the correction of the algorithm.

$\endgroup$
2
  • 1
    $\begingroup$ I highly appreciate you for this answer. It looks great. But I have two problems. 1) How can I find the leaf with maximum depth. 2) I guess I can't understand the correct meaning of this sentence: "or by finding a leaf of maximum depth in the tree rooted in $x$". You mean I reverse the tree and assume that $x$ is the root an do what I did for step 1? $\endgroup$ Jan 1 at 0:50
  • 1
    $\begingroup$ You can compute the depth of each node, either by running a BFS from the root, or (it is the same idea) by computing it recursively: the depth of a node is $1$ plus the depth of its parent (except for the root, which is of depth $0$). And yes, given a tree, you can compute the tree rooted in any node in linear time. $\endgroup$
    – Nathaniel
    Jan 1 at 1:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.