Maintaining the diameter of a growing tree in O(log n) time

2024-09-03

A tree is a connected undirected graph with nodes and edges. The diameter of a tree is the largest distance between two nodes in the tree.

We define a growing tree as follows: at each moment, a new node is inserted into the tree, and is connected to some node in the original tree. What is the diameter of the new tree?

Let be the path such that the length of is the diameter of the original tree. A key observation is that if are the endpoints of , then for the new tree, the endpoints of the new path for the new diameter must be or .

The proof is rather simple. The distance between is actually the length of . By the definition of the tree diameter, it is also the largest distance between two nodes in the original tree. Since the distances between two nodes do not change in the original and new tree, the only candidate nodes to be the new endpoints could only be (for other nodes, since they have the same distances which are not larger than , we could just ignore them).

Therefore, to derive the new diamter, we only need to maintain for each moment, and compute the distances between and after each moment, where the largest distance is the new diameter. The distance between could be computed by , where is the depth of the node and is the lowest common ancestor of two nodes, and other distances could be computed similarly. The depth of the new node could be maintained in time for each moment. Maintaining and computing could be done in time for each moment. As a result, we could maintain the diameter of a growing tree in time.