Diameter of a Binary Tree | Class containing left and right child of current node and key value ; Class to print the Diameter ; The function Compute the " height " of a tree . Height is the number of nodes along the longest path from the root node down to the farthest leaf node . ; base case tree is empty ; If tree is not empty then height = 1 + max of left height and right heights ; Method to calculate the diameter and return it to main ; base case if tree is empty ; get the height of left and right sub - trees ; get the diameter of left and right sub - trees ; Return max of following three 1 ) Diameter of left subtree 2 ) Diameter of right subtree 3 ) Height of left subtree + height of right subtree + 1 ; A wrapper over diameter ( Node root ) ; Driver Code ; creating a binary tree and entering the nodes ; Function Call
class Node { int data ; Node left , right ; public Node ( int item ) { data = item ; left = right = null ; } } class BinaryTree { Node root ; static int height ( Node node ) { if ( node == null ) return 0 ; return ( 1 + Math . max ( height ( node . left ) , height ( node . right ) ) ) ; } int diameter ( Node root ) { if ( root == null ) return 0 ; int lheight = height ( root . left ) ; int rheight = height ( root . right ) ; int ldiameter = diameter ( root . left ) ; int rdiameter = diameter ( root . right ) ; return Math . max ( lheight + rheight + 1 , Math . max ( ldiameter , rdiameter ) ) ; } int diameter ( ) { return diameter ( root ) ; } public static void main ( String args [ ] ) { BinaryTree tree = new BinaryTree ( ) ; tree . root = new Node ( 1 ) ; tree . root . left = new Node ( 2 ) ; tree . root . right = new Node ( 3 ) ; tree . root . left . left = new Node ( 4 ) ; tree . root . left . right = new Node ( 5 ) ; System . out . println ( " The ▁ diameter ▁ of ▁ given ▁ binary ▁ tree ▁ is ▁ : ▁ " + tree . diameter ( ) ) ; } }