Diameter of a binary tree

As long as every node has a reference to its parent, then it's easy. If you have to rebuild the tree, then yes it will be a little messy.

Can you expand on your algorithm and what the runtime would be?

Here is the outline code for the algorithm mentioned in the link.

public static void farthestFrom(Node n, Object[] ret) {

Node f = n;

stack s = new stack;

s.push(n);

int dist = 0;

int maxDist = 0;

while (!s.isEmpty()) {

Node m = (Node) s.pop();

m.visited = true;

boolean b = false;

if (m.parent != null && !m.parent.visited) {

b = true;

s.push(m);

}

for each child (c) of m {

if (!c.visited) {

b = true;

s.push(c);

}

}

if (b) {

dist++;

if (dist > maxDist) {

maxDist = dist;

f = (Node) s.peek();

}

}

else {

dist--;

}

}

ret[0] = f;

ret[1] = new Integer(maxDist);

}

Tree tree = ...;

Object[] ret = new Object[2];

farthestFrom(tree.root, ret);

farthestFrom((Node) ret[0], ret);

System.out.println("diameter: " + ret[1]);

rkippena at 2007-7-15 23:14:58 >

> Can you expand on your algorithm and what the runtime would be?

(int, int) findDiameterInner(Node n)

{

if (n == null) return (0, 0)

(a, b) = findDiameterInner(n.leftChild);

(c, d) = findDiameterInner(n.rightChild);

depth = max(a, c) + 1;

dia = max(b, d, a + c);

return (depth, dia);

}

int findDiameter(Node root)

{

(depth, dia) = findDiameterInner(root);

return dia;

}

Time is O(n), because findDiameterInner is called once on each node and, other than recursive calls, takes constant time.

YAT_Archivista at 2007-7-15 23:14:58 >

> If it wasn't a binary tree, then the diameter computation would have to be modified to add the

> maximum depths I think.

I concur.

> Maybe the algorithm that reroots the tree is used to find the actual path, not just the diameter.

I could modify mine to do that by passing back more information. Precisely what information depends on whether nodes have references to their parents or not, but it would still be O(n) overall.

I do wonder whether the rerooting algorithm might work for general graphs, but I'm not going to try to prove or disprove it.

YAT_Archivista at 2007-7-15 23:14:58 >