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.

Solution:

• The diameter of a tree T is the largest of the following quantities:
  • the diameter of T’s left subtree
  • the diameter of T’s right subtree
  • the longest path between leaves that goes through the root of T

Algorithm:

1.  Traverse tree in PostOrder
   1. If node is null then
      1. return 0
   2. diameterOfLeftSubTree = recursively call with node.left
   3. diameterOfRightSubTree = recursively call with node.right
   4. longestPathBetweenLeaves = heightOfLeftSubTree + heightOfRightSubTree + 1
   5. return max (diameterOfLeftSubTree, diameterOfRightSubTree, longestPathBetweenLeaves)

Time Complexity: O(n^2)

Latest Source Code:
Github: BinaryTreeMaxWidthFinder.java

Output:

               1                               
              / \               
             /   \              
            /     \             
           /       \            
          /         \           
         /           \          
        /             \         
       /               \        
       2               3               
      / \                       
     /   \                      
    /     \                     
   /       \                    
   4       5                       
  /       /                     
 /       /                      
 8       6                       
          \                     
          7                     
                                                                
Diameter : 6
       1               
      / \       
     /   \      
    /     \     
   /       \    
   2       3       
  /         \   
 /           \  
 4           5   
/ \             
6 7             
                                
Diameter : 6