Diameter of a Binary Tree

Diameter of a Binary Tree

The diameter of a tree (sometimes called the width) is the number of nodes on the longest path between two leaves in the tree. The diagram below shows two trees each with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).

Solution

This problem is similar to the "Binary Tree Max Path Sum" problem that we discussed in previous post.

The diameter of a tree T is

Diameter(T) = max( Diameter(T.left), Diameter(T.right), Height(T.left)+Height(T.right)+1 )

We can "translate" this formula to code with a recursive helper method to get height of a given tree, height(TreeNode root). But you may notice that height of subtrees have been repeatedly computed.
Suppose the tree is of height m and root is at level 0. It visits each node at i-th level i+1 times. The worst case running time is O(n^2).

To reduce the running time, either we calculate heights, store height of each node in a HashMap, and run another pass to calculate the diameter; or we calculate height and diameter in the same recursion.
Both algorithms have worst-case running time O(n) but the former one requires O(n) extra space.

Here is an implementation for latter algorithm which runs in time O(n) with O(1) space.
Notice that Java cannot return two values and pass-in arguments are passed in by reference. So, we create an object to store height and diameter so that they could be updated through recursions.

 private class Data {  
   public int height;  
   public int diameter;  
 }  
   
 private void diameter(TreeNode root, Data d) {  
   if (root == null) {  
     d.height = 0; d.diameter = 0; return;  
   }  
   diameter(root.left, d); // get data in left subtree  
   int hLeft = d.height;  
   int dLeft = d.diameter;  
   diameter(root.right, d); // overwrite with data in right tree  
   d.diameter = Math.max(Math.max(dLeft, d.diameter), hLeft+d.height+1);  
   d.height = Math.max(hLeft, d.height) + 1;  
 }  
   
 public int diameter(TreeNode root) {  
   Data data = new Data();  
   diameter(root, data);  
   return data.diameter;  
 }