Path of the diameter of a binary tree

Question

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?

Thanks

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Answer 1

You have two options: A) Think. B) Search. Among the first few google hits you can find this: http://login2win.blogspot.hu/2012/07/print-longest-path-in-binary-tree.html

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:

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.
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.
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.

Path of the diameter of a binary tree

Sign up