Make delicious recipes!

Tree diameter



Diameter of a binary tree is defined as the longest path from a leaf node to another leaf node.
For example, in the below tree:

      7
     /  \
    5    14
        /  \
       11  20
      /      \
     10      25
    /       /
   9       22

The diameter is from leaf 9 to leaf 22 and its length is 7.



Solution: Note that the diameter may not pass through the root-node (as shown above)


Also, the ends of the diameter will be such that one of them lies in the
left subtree of a node and the other end lies in the right subtree of the same node.
Otherwise the diameter will tend to appear like a knot.
For example, if the diameter of the above tree were to be: 9 -> 14 -> 7 -> 14 -> 22,
then 14 -> 7 -> -> 14 nodes would appear like a knot and that is not allowed to be in a diameter.


So, there will be one node whose left and right legs of deepest height would form the diameter.
Our task is to find that node for which 1 + diameter(left) + diameter(right) is the maximum.


/**
 * Diameter at each node could be different from
 * the diameter of its immediate child nodes.
 */
int diameter (TreeNode n)
{
    if (n == null)
        return 0;

    int currDia = 1 + depth(n.left) + depth(n.right);

    return Math.max(
        currDia,
        Math.max(diameter(n.left), diameter(n.right))
    );
}

/**
 * Normal depth finding function
 */
int depth(TreeNode n)
{
    if (n == null)
        return 0;

    return 1 + Math.max(depth(n.left), depth(n.right)); 
}


But there's always room for optimization!!


See the calls to depth() function.

At every node, depth() is called and same nodes are being traversed multiple times due to this.


To optimize, we can do either of these:
  1. Return height also from the diameter() function by changing the return type to Pair<Integer, Integer>
  2. Store height for each node in the tree itself and calculate it only once before calling diameter.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal