Node at a longest distance from another node in a tree

Question

Given a input a tree we need to answer the queries of the type,

a) given a node of the above tree, which is the node which is at the longest distance from that node.

b) remove a particular set of edges from the tree.

I have been trying this for a long time but the best solution I could come up with was,

For a query of type a call dfs function which would return the farthest node in O(N), but i need to do better. For a query of type b, just update the tree [remove edge if exists].

So my solution above is roughly O(K*N) where K is the number of queries and N is the number of Nodes.

Answer 1

Since your tree is a general tree, i.e., it has no notion of being balanced or even having a root, the best you can do for a one-off query is O(n). However, I think you can set up the tree once taking O(n) time and then have each following query take constant time.

The idea is to find the "middle" of the tree which separate the tree into to roughly equal sized trees, calling the parts arbitrary, e.g., left and right. You then label all nodes in their respective parts with the part they are in and store a left and a right node which are farthest away from the middle. When you get a query for a node you just look at the node's label and report the stored node on the other side.

Given the comment [and the unwarranted downvote] it seems the solution requires a bit more explanation. First off, the furthest apart node for a given node is, in general, not unique. Imagine for example a path with exactly three nodes. There are two furthest away nodes for the middle node. Either one of them is a solution. Based on that, the idea is to find a node in the tree which is located in the middle of the path between the two farthest apart nodes in the tree (of the distance between these nodes is odd, a node on either side can be chosen such that the distances differ by just one): If the farthest apart nodes are l nodes apart, the middle node has a path of length l/2 to both of them or a path of l/2 to one and l/2+1 to the other.

Using this middle node to separate the tree into two halves, randomly called the left and the right half, makes it possible to determine the farthest apart node for any given node if each node knows whether it is in the left or the right half: the longest path will go through the middle node into the other half and from there to the node farthest away from the middle. Let's call the length of the longest path in the left part ll and the length of the longest path in the right part lr. Without loss of generality, have lr < ll (just swap the names around). The respective farthest apart nodes from the middle are called nl and nr. Note that it is OK if there are multiple subtrees leading from the middle node which are considered part of the right part as long as one of the longest path (or the longest path if it is unique) is in the left part.

There are three cases to consider when you want to state the furthest apart node from a node n:

1. The node n is the middle node. In this case, the furthest apart node is clearly nl.
2. The node n is in the right part of the tree. The longest path you can construct travels to the middle and then to nl, i.e., the furthest apart node is clearly nl, too
3. The node n is in the left part of the tree. Again, the longest path you can construct travels to the middle but from there to nr.

The only question remaining is how to find the middle node in O(n) time:

1. Find all leaf nodes and put them into a queue, labeling them with 1 and giving them a distance of 0. This can be done in O(n) time [and space].
2. Read (but don't extra, yet) the first node from the queue and find all adjacent nodes. If there is a node with a label which is less than its number of adjacent nodes, increment the label. If the label now matches the number of adjacent nodes, add the node to the queue and give it a distance one bigger than the first node from the queue.
3. If there is only one node in the queue, this node is the middle node and this step terminates.
4. Otherwise, extract the front node and continue processing the queue (i.e., step 2).

As a final pass, find the adjacent node with the biggest distance label and consider the tree hanging off this node the left tree. While labeling the nodes as left nodes with a BFS keep track of the last node in the queue to find nl. Consider all other subtrees right trees and label them with BFS, too, as right nodes, also finding nr.

I guess, the preprocessing of the tree can be done more elegantly, possibly using few passes, too, but I'm sure the above approach does work.