• Post Reply Bookmark Topic Watch Topic
  • New Topic

Diameter of a tree  RSS feed

 
Leon Leung
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Leon,

Welcome to JavaRanch!

"Diameter"? Do you mean "depth?"
 
Jeff Albertson
Ranch Hand
Posts: 1780
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!