How to Find Diameter Of Binary Tree?

Find Diameter of Binary Tree is the most frequently asked software interview question nowadays. It tests your skill and understanding of the Binary Tree and its height calculation.

What is Diameter of the Binary Tree?

The number of nodes on the longest path between two end nodes is the diameter (also known as width) of a tree.

The leaves that create the ends of the longest path are shaded in the diagram below, which displays two trees each with a diameter of nine (note that there is more than one path in each tree of length 6, but no path longer than six nodes).

How to Find Diameter Of Binary Tree

Algorithm to Find Diameter of Binary Tree

The algorithm behind finding the diameter of the binary tree is very simple. All you need to do is find the height of the left subtree and the max height of the right subtree.

Once you have a max height of both subtrees at those heights and compare with the current diameter if that is less than the current diameter update the diameter values to the current diameter value.

Since the maximum height of subtree needs to be passed through the root node hence the distance between the maximum height of the left subtree and the maximum height of the right subtree plus one for the root node will be the diameter of the binary tree.

But the above algorithm can take O(n2). Since we are taking the height of the left and right subtree two times. To optimize the solution we need to calculate the height of both the subtree in one iteration. And for this, we can use postorder traversal or preorder traversal for the binary tree.

Let us see the actual running code below and understand. As in the below code, we are using post-order traversal to find the diameter of the Binary tree.

C++ Code for Diameter of Binary Tree [Optimized]

// Optimized version of Code to Find the Diameter of Binary Tree.
// This code runs at O(n) time where n is the number of nodes.
#include <bits/stdc++.h>
using namespace std;

// Helper function to Create New Node for Binary Tree.
struct TreeNode {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
  
int diameterOfBinaryTree(TreeNode* root, int* height)
{
    // lHeight is Height of left subtree
    // rHeight is Height of right subtree
    int lHeight = 0, rHeight = 0;
  
    // lDiameter is diameter of left subtree
    // rDiameter is Diameter of right subtree
    int lDiameter = 0, rDiameter = 0;
  
    if (root == NULL) {
        *height = 0;
        return 0; // diameter is also 0
    }
  
    // Get the heights of left and right subtrees in lHeight and
    // rHeight And store the returned values in lDiameter and
    // rDiameter
    lDiameter = diameterOfBinaryTree(root->left, &lHeight);
    rDiameter = diameterOfBinaryTree(root->right, &rHeight);
  
    // Height of current node is max of heights of left and
    // right subtrees plus 1
    *height = max(lHeight, rHeight) + 1;
  
    return max(lHeight + rHeight + 1, max(lDiameter, rDiameter));
}
 
// Main Code for Testing
int main()
{
  
    /* Constructed binary tree is
            1
            / \
        2     3
        / \
    4     5
    */
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
     
    int height = 0;
    // Function Call
    cout << "Diameter of the given binary tree is " << diameterOfBinaryTree(root, &height);
  
    return 0;
}
 
// This code is contributed by probinsah.

Python Code for Diameter of Binary Tree

The below example in python is a little different approach.

#Here root is the root of given tree already created using the structure or class below.
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.ans = 0
        
        def height(p):
            # it's custom to define the height of an empty tree to be -1. This also fixes the off-by-one error I mentioned.
            if not p: return -1       
                            
            left, right = height(p.left), height(p.right)
            
            # the "2+" accounts for the edge on the left plus the edge on the right. This change is required to account for 
            # the fact that we updated the height of an empty tree to be -1. 
            self.ans = max(self.ans, 2+left+right)   
            
            return 1+max(left, right)
            
        height(root)
        return self.ans

JAVA Code for Diameter of Binary Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        int[] diameter = new int[1];
        height(root, diameter);
        return diameter[0];        
    }

    private int height(TreeNode node, int[] diameter) {
        if (node == null) {
            return 0;
        }
        int lh = height(node.left, diameter);
        int rh = height(node.right, diameter);
        diameter[0] = Math.max(diameter[0], lh + rh);
        return 1 + Math.max(lh, rh);
    }
}

Output: Below is the output for the above input tree.

How to Find Diameter Of Binary Tree

Time Complexity

Time Complexity for the above solution code is O(n), where n is the number of nodes present in the binary tree.

Below is the time and memory it took for the complete program to run on the server of LeetCode.

How to Find Diameter Of Binary Tree?

If you liked the answer then please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.

Leave a Comment