user1439691 user1439691 - 4 years ago 107
C Question

Path of the diameter of a binary tree

I have a binary tree and a method for the size of the longest path (the diameter):

int diameter(struct node * tree)

if (tree == 0)
return 0;

int lheight = height(tree->left);
int rheight = height(tree->right);

int ldiameter = diameter(tree->left);
int rdiameter = diameter(tree->right);

return max(lheight + rheight + 1, max(ldiameter, rdiameter));

I want the function to return also the exact path (list of all the nodes of the diameter).
How can I do it?


Answer Source

You have two options: A) Think. B) Search. Among the first few google hits you can find this:

Choose A) if you want to learn, choose B) if you do not care, only want a quick, albeit not necessarily perfect solution.

There are many possible solutions, some of them:

  1. In a divide and conquer approach you will probably end up with maintaining the so far longest paths on both sides, and keep only the longer.
  2. The quoted solution does two traversals, one for determining the diameter, and the second for printing. This is a nice trick to overcome the problem of not knowing whether we are at the deepest point in approach 1.
  3. Instead of a depth first search, do a breadth first one. Use a queue. Proceed level by level, for each node storing the parent. When you reach the last level (no children added to queue), you can print the whole path easily, because the last printed node is on (one) longest path, and you have the parent links.
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download