Diameter of a Binary Tree

In this problem, we are given input as the reference to the root of a binary tree. We need to find the diameter of the tree. We solve this using two approaches:

• Approach 1: Using recursion
• Approach 2: Using DFS

A tree is an extensively used data structure in the world of programming. Every node in a tree can have more further subdivisions. The bottom-most nodes of a tree that have no sub-divisions, are called the leaf nodes.

DIAMETER OF A TREE: It is defined as the number of nodes on the longest path between 2 nodes.This path may or may not pass through the root of the tree.This path includes two leaf nodes. It is also known as the width of a tree.

There can be two possibilities for the longest path of a tree

1. It passes through the root.
2. It doesn't pass through the root.

In the first example, the diameter is 6, and for the second one, diameter is 5.
There can be more than one longest path, but the diameter will always be maximum.

This problem can be solved with various methods:

Approach 1: Use recursion

We use recursion to calculate the height of a subtree and the diameter. So, we make a recursive function i.e diameter(struct node* tree)

We can consider that the diameter upto any given node will be the sum of the height of its left and right subtrees and 1.

Hence,
Diameter = Left subtree height + Right subtree height + 1.

1. If the node that is passed in the recursive function is null, then return zero.
2. Calculate the height of the left subtree.
3. Calculate the height of the right subtree.
4. Calculate the diameter of the left subtree using recursive call till node becomes null.
5. Calculate diameter of the right subtree using recursion till node becomes null.
6. If the diameter passes through the root node, then the no. of nodes in the path will be : Left subtree height + Right subtree height + 1
7. However, if it doesn't pass through the root node, then the diameter will be max(left subtree diameter, right subtree diameter)
8. The final diameter will be the maximum value of step 6 and step 7 , and this value will be returned.

This process is continued in recursion till we encounter NULL nodes.

Time complexity : O(n^2)
Space Complexity: O(log n), if a balanced tree, O(n) otherwise. Space complexity is due to recursion.

Code:

//Java program to find the diameter of a Binary Tree 
  
// Structure of the tree 
class Node { 
    int data; 
    Node left, right; 
  
    public Node(int item) 
    { 
        data = item; 
        left = right = null; 
    } 
} 
  
// Class to print the Diameter 
class BinaryTree { 
    Node root; 
  
    // Method to calculate the diameter and return it to  main 
    int diameter(Node root) 
    { 
        // base case if tree is empty 
        if (root == null) 
            return 0; 
  
        // get the height of left and right sub trees 
        int lheight = height(root.left); 
        int rheight = height(root.right); 
  
        // get the diameter of left and right subtrees 
        int ldiameter = diameter(root.left); 
        int rdiameter = diameter(root.right); 
  
        /* 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 
         */
        return Math.max(lheight + rheight + 1, 
                        Math.max(ldiameter, rdiameter)); 
    } 
  
    // A wrapper over diameter(Node root) 
    int diameter() { return diameter(root); } 
  
    // function to calculate height of the tree
    static int height(Node node) 
    { 
        // base case tree is empty 
        if (node == null) 
            return 0; 
  
        // If tree is not empty then height = 1 + max of 
        //  left height and right heights 
        return (1
                + Math.max(height(node.left), 
                           height(node.right))); 
    } 
  
    // Driver Code 
    public static void main(String args[]) 
    { 
        // creating a binary tree and entering the nodes 
        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); 
  
        // Function Call 
        System.out.println( 
            "The diameter of given binary tree is : "
            + tree.diameter()); 
    } 
}

Output:

The diameter of the given binary tree is 4

Approach 2: Using DFS

We can also use the Depth Fisrt Search algorithm to calculate the diameter. Since the longest path always occurs between 2 leaf nodes, if we calculate the farthest node from a leaf node, then we can find the longest path in the tree.

We perform the following steps:

1. Start at the root node and find the farthest node from it using DFS.
2. Consider this farthest node to be the start node of the longest path.
3. Find the farthest node from the start node using DFS.
4. This farthest node will be the end node of the longest path.

Time Complexity: O(n)
Space complexity: O(n)

Code:

// Java program to find diameter of a tree using DFS. 
import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 
public class Diametre_tree { 
   
    // Used to track farthest node. 
    static int x; 
    static int maxCount; 
    static List<Integer> adj[]; 
      
    // Sets maxCount has maximum distance from node
    static void dfsUtil(int node, int count,  
                         boolean visited[], 
                       List<Integer> adj[]) 
    { 
        visited[node] = true; 
        count++; 
          
        List<Integer> l = adj[node]; 
        for(Integer i: l) 
        { 
            if(!visited[i]){ 
                if (count >= maxCount) { 
                    maxCount = count; 
                    x = i; 
                } 
                dfsUtil(i, count, visited, adj); 
            } 
        } 
    } 
       
    //Recursuve function for DFS traversal 
    static void dfs(int node, int n, List<Integer> 
                                       adj[]) 
    { 
        boolean[] visited = new boolean[n + 1]; 
        int count = 0; 
       
        // Mark all the vertices as not visited 
        Arrays.fill(visited, false); 
       
        // Increment count by 1 for visited node 
        dfsUtil(node, count + 1, visited, adj); 
          
    } 
       
    // Returns diameter of binary tree represented 
    // as adjacency list. 
    static int diameter(List<Integer> adj[], int n) 
    { 
        maxCount = Integer.MIN_VALUE; 
       
        /* DFS from a random node and then see 
        farthest node X from it*/
        dfs(1, n, adj); 
       
        /* DFS from X and check the farthest node 
        from it */
        dfs(x, n, adj); 
       
        return maxCount; 
    } 
       
    //Driver code
    public static void main(String args[]) 
    { 
        int n = 5; 
       
        /* Constructed tree is 
             1 
            / \ 
            2    3 
           / \ 
          4   5 */
        adj = new List[n + 1]; 
        for(int i = 0; i < n+1 ; i++) 
            adj[i] = new ArrayList<Integer>();  
       
        /*create undirected edges */
        adj[1].add(2); 
        adj[2].add(1); 
        adj[1].add(3); 
        adj[3].add(1); 
        adj[2].add(4); 
        adj[4].add(2); 
        adj[2].add(5); 
        adj[5].add(2); 
          
        /* maxCount will have diameter of tree */
        System.out.println("Diameter of the given tree is " + diameter(adj, n)); 
    } 
} 

Output:

Diameter of the given tree is 4

Comparison of different solutions

Use cases of finding diameter of a tree:

1. The average diameter is measured to find the route of direct inter-processor communication, without going through a center, within a network of any structure.

2. The DADO parallel computer uses a binary tree interconnection network for the rapid execution of rule-based, AI-oriented software.