Binary Tree: Program to print the diameter of a binary tree

Write a program to print the diameter of a binary tree

Diameter of a binary tree is basically a total number of nodes in the longest path from one leaf node to another which can contain root or sometimes not

There are three cases for finding the diameter of binary tree
- Longest path falls in the left subtree which do not contain root
- Longest path falls in the right subtree which do not contain root
- Longest path falls in both the subtree and passes through root

The solution is to find maximum of
- diameter of left subtree
- diameter of right subtree
- height of left subtree + height of right subtree + 1

Which ever of these is maximum is our answer.

Diagram

Algorithm

1. If temp is NULL then simply return 0
2. Declare option1 as int call diamterOfTree function for temp.left
3. Declare option2 as int call diamterOfTree function for temp.right
4. Declare option3 as int and store height of left-subtree + height of right-subtree + 1
5. Result will equal to maximum of option1, option2 and option3
6. Return result

Complexity

Time Complexity : O(n^2) , where n is the number of nodes in binary tree
Space Complexity : O(n) for recursive call stack

Java Code

class BinaryTreeDiameter{
 
        static class Node {
     
            int data;
            Node left, right;
     
            Node(int element) {
                data = element;
                left = right = null;
            }
        }
     
        Node root;
     
        public static Node constructBinaryTree(int[] arr, int i) {
            Node root = null;
            if (i < arr.length) {
                root = new Node(arr[i]);
     
                root.left = constructBinaryTree(arr, 2 * i + 1);
                root.right = constructBinaryTree(arr, 2 * i + 2);
            }
            return root;
        }
     
        public int heightofTree(Node current) {
            if (current == null)
                return 0;
            int leftHeight = heightofTree(current.left);
            int rightHeight = heightofTree(current.right);
     
            int result = Math.max(leftHeight, rightHeight) + 1;
            return result;
     
        }
     
        public int diameterofTree(Node temp) {
            if (temp == null) {
                return 0;
            }
     
            int option1 = diameterofTree(temp.left);
            int option2 = diameterofTree(temp.right);
            int option3 = heightofTree(temp.left) + heightofTree(temp.right) + 1;
     
            int result = Math.max(option3, Math.max(option1, option2));
            return result;
     
        }
     
        public static void main(String args[]) {
            BinaryTreeDiameter tt1 = new BinaryTreeDiameter();
     
            int[ ] bstElements1 = new int[] { 50, 20, 30, 10, 200, 70, 90 };
            tt1.root = tt1.constructBinaryTree(bstElements1, 0);
            System.out.print("Diameter of Given Tree is : ");
            System.out.println(tt1.diameterofTree(tt1.root));
     
        }
    
  }

Output

Diameter of Given Tree is : 5