programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Diameter of a tree

Leon Leung
Greenhorn
Posts: 2
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

Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
Hi Leon,

Welcome to JavaRanch!

"Diameter"? Do you mean "depth?"

Jeff Albertson
Ranch Hand
Posts: 1780
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.

Leon Leung
Greenhorn
Posts: 2
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

Jeff Albertson
Ranch Hand
Posts: 1780
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 ]