CODEWITHSUNDEEP
c++algorithmtreegraph-theorybreadth-first-search
A Zhang
A Zhang

Reputation: 23

Find the maximum distance for all nodes in a tree in linear time

Define Maximum Distance of a node to be the maximum of the distances between that node and all other nodes in the tree. My problem is to find and print the maximum distance for all nodes within a tree (not necessarily binary or anything). Basically, for each node, I need to print out the maximum distance that node has between the node we are looking at, and any other node within the tree. The runtime is expected to be O(n).

My best approaches all take O(N^2) time and I'm not sure where else to go with this problem. I currently run BFS on every node in the tree to find the max distance for each node in the tree, but I think a better approach might be to use some form of dynamic programming. I'm not sure though.

Thanks for any help in advance.

Upvotes: 0

Views: 1984

Answers (1)

kraskevich
kraskevich

Reputation: 18566

Let's pick an arbitrary node as a root. Now we've got a rooted tree.

Finding the furthest node in a subtree is straightforward: it's just the highest leaf (a subtree dynamic programming for the furthest node in a subtree would work).

But what if it's not in a subtree? It cannot happen for the root, so we have the answer for it. Let's assume that we want to go to its child. We need to consider furthest leaves in subtrees of all children of the root except for this one. Iterating over all children naively would give n^2 time complexity in the worst case. But we can find the optimal child except for a fixed one by storing two best children. We can do the same thing for any other node, so it works in linear time.

Upvotes: 0

Related Questions