Print a path consisting of nodes matching the diameter of the BST

Question

I know how to find the diameter of a BST.

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)); } int height(struct node* node) { if(node == NULL) return 0; return 1 + max(height(node->left), height(node->right)); } 

What changes should I make to the code to print the path, that is, the nodes corresponding to the diameter of the tree in a sequence from one leaf node, to another leaf node diameter.

For instance: -

  8 / \ 1 12 \ / 5 9 / \ 4 7 / 6 

output should be 6 7 5 1 8 12 9

Answer 1

Here is an algorithm for finding the maximum depth of a binary tree:

• Let varible exist with the name max_height .
• Initialize to zero.
• Let there be a variable called depth .
• Initialize depth to zero.
• When moving to a subtree, increment depth .
• If depth greater than max_height , set max_height to depth .
• Returning from a subtree, decrease the depth .

This assumes that the reader knows how to navigate the binary tree; which is the subject of another post.

Answer 2

 struct node { node* left,right; int data; }; struct path { node *nodepointer; int length; }; int flag=0; node *x,*y,*lca; path *printpath(node *leaf,int d) { if(flag==0) { path *dia= new path; dia->length=0; dia->nodepointer=NULL; if(leaf==NULL) return dia; path *a=new path; path *b=new path; a=printpath(leaf->left,d); b=printpath(leaf->right,d); if(a->length + b->length + 1 == d ) { lca=leaf; x=a->nodepointer; y=b->nodepointer; flag=1; } dia->length=max(a->length,b->length)+1; if(a->length > b->length && a->nodepointer!=NULL) { dia->nodepointer=a->nodepointer; } if(b->length >= a->length && b->nodepointer!=NULL) { dia->nodepointer=b->nodepointer; } if(a->nodepointer==NULL && b->nodepointer==NULL) { dia->nodepointer=leaf; } return dia; } }