The most distant node for each node

Question

Is there any way to find the most distant node for every node in binary tree. I know about problem of diemeter of the tree, but that is query about every node. I would like to have algorithm working in O(nlogn) for n-node tree.

Answer 1

In two steps:

• Calculate the most distant child and its distance for each node. This can be done by traversing the tree (O(n)) post-order.

• For each node: check the most distant child for this node and each of its parents (adding one extra distance as you walk toward the root). Pick the largest. O(n logn).

Modification: If you store the most distant child and its distance for both the left and right subtrees, you can traverse the tree pre-order and get all the results in O(n).

Example (without marking which node is the most distant.. implementation detail):

       3.2       root
      /   \
     1*2  0.1
     / \    \
   0.0 1.1  0.0
       / \
     0.0 0.0

Starting from the root - longest distance through parent is 0.

• The longest distance is max(0,2,3) = 3.
• Recursing to left: passing max(0,2)+1 as the longest distance through parent.
• Recursing to right: passing max(0,3)+1 as the longest distance through parent.

At any point there are three possibilities: longest route goes though the parent, it's in the left subtree or in the right subtree. All these distances are readily available when visiting the node.