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



Thanks for feedback.



Read More....
Check if a binary tree is a min heap
Check if a binary tree is symmetric or mirror of itself
Check if a binary tree is symmetric or mirror of itself - iterative
Create a mirror of binary tree - Iterative approach
Create a mirror of binary tree - Recursive approach
Find the height of binary tree - Iterative approach