Monday, 1 October 2012

Diameter and maximum distance between two nodes in a Binary tree.

/*
  Function to find out maximum distance between two nodes in a binary tree.
  Ds for tree could be found here: Ds for Tree
*/

public int height(Node root){
        if(root==null)
            return 0;
        else
            return (1+max(height(root.getLeft()),height(root.getRight())));
    }
   
    public int max(int a, int b){
        return a>b?a:b;
    }
   
    public int diameter(Node root){
        if(root==null)
            return 0;
        else{
            int lh=height(root.getLeft());
            int rh=height(root.getRight());
           
            int ld=diameter(root.getLeft());
            int rd=diameter(root.getRight());
           
            return( max(1+lh+rh,max(ld,rd)));  //add 1 to the result if counting current node as well.
        }          
    }