Leon Leung

Greenhorn

Posts: 2

posted 12 years ago

Hi all,

my professor ask the class to use divide and conquer to compute the diameter of a rooted binary tree. How should the algorithm work? I think it should recursively go to the subtree until it reach the leaves, but I am not sure what I need to return to the parents, or I am in the wrong track? any suggestion will help

Thank You

my professor ask the class to use divide and conquer to compute the diameter of a rooted binary tree. How should the algorithm work? I think it should recursively go to the subtree until it reach the leaves, but I am not sure what I need to return to the parents, or I am in the wrong track? any suggestion will help

Thank You

Jeff Albertson

Ranch Hand

Posts: 1780

posted 12 years ago

Or is this your definition of diameter:

Let G be a graph with nodes in V. For two nodes a,b in V we define the distance d(a,b) as the length

of the shortest path from a to b. The diameter of G is defined as being the maximal distance in the graph.

Let G be a graph with nodes in V. For two nodes a,b in V we define the distance d(a,b) as the length

of the shortest path from a to b. The diameter of G is defined as being the maximal distance in the graph.

There is no emoticon for what I am feeling!

Leon Leung

Greenhorn

Posts: 2

Jeff Albertson

Ranch Hand

Posts: 1780

posted 12 years ago

Reread what I wrote. The Diameter is the *maximal* distance in the graph,

across all node pairs.

Now does you professor what you to find the longest simple path, or the

hint: the path either includes the root, or it doesn't. :roll:

[ November 01, 2005: Message edited by: Jeff Albrechtsen ]

Originally posted by Leon Leung:

my professor want us to find the longest simple path between 2 leaves node, not shortest simple path. Sometimes it is as known as width

Reread what I wrote. The Diameter is the *maximal* distance in the graph,

across all node pairs.

Now does you professor what you to find the longest simple path, or the

*length*of the longest simple path? Either way, here's a divide-and-conquer

hint: the path either includes the root, or it doesn't. :roll:

[ November 01, 2005: Message edited by: Jeff Albrechtsen ]

There is no emoticon for what I am feeling!