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

isaach1000 · Accepted Answer · 2013-05-05 08:51:02Z

1

Add a property struct node * next to the node struct. Before the return statement, add a line like this tree->next = (ldiameter > rdiameter ? tree->left : tree->right) to get the longer path node as the next node. After calling diameter(root), you should be able to iterate through all of the next nodes from the root to print the largest path.

answered May 5, 2013 at 8:51

isaach1000

1,8391 gold badge14 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

paramvir · Accepted Answer · 2017-02-07 06:47:49Z

I think the following may work... compute the diameter as follows in O(N) time.

// this is a c++ code
int findDiameter(node *root, int &max_length, node* &max_dia_node, int parent[], node* parent_of_root){
    if(!root) return 0;
    parent[root->val] = parent_of_root->val;
    int left = findDiameter(root->left, max_length);
    int right = findDiameter(root->right, max_length);
    if(left+right+1 > max_length){
        max_dia_node = root;
        max_length = left+right+1;
    }
    return 1 + max(left,right);
}

So in this function number of things is happening. First max_length is calculating the max diameter of the tree. And along with that I am assigning the max_dia_node to this node.

This is the node through which I will have my max diameter pass through.

Now using this information we can find the max depth left child and right child of this node (max_dia_node). From that we can have the actual nodes via "parent" array.

This is two traversal of the tree.

jmihalicza · Accepted Answer · 2013-05-04 23:17:36Z

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.

Collectives™ on Stack Overflow

Path of the diameter of a binary tree

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related