c++ - Path of the diameter of a binary tree -

i have binary tree , method size of 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 function return exact path (list of nodes of diameter). how can it?

thanks

you have 2 options: a) think. b) search. among first few google hits can find this: http://login2win.blogspot.hu/2012/07/print-longest-path-in-binary-tree.html

choose a) if want learn, choose b) if not care, want quick, albeit not perfect solution.

there many possible solutions, of them:

1. in divide , conquer approach end maintaining far longest paths on both sides, , keep longer.
2. the quoted solution 2 traversals, 1 determining diameter, , second printing. nice trick overcome problem of not knowing whether @ deepest point in approach 1.
3. instead of depth first search, breadth first one. use queue. proceed level level, each node storing parent. when reach last level (no children added queue), can print whole path easily, because last printed node on (one) longest path, , have parent links.