Diameter of Binary Tree | LeetCode | Solution Explained

Finding the Diameter of Binary Tree is a classic problem when it comes to understanding the basics of trees and using DFS. In this writeup, I explain how we can go about solving this problem. Problem Link.

Problem Discussion

• We are given a binary tree
• We want to find its diameter – the length of the longest path between any two nodes

The question mentions:  This path may or may not pass through the root. Wait what? That looks oddly specific. Let’s try to build a test case that has this condition.

In this case, we can clearly bypass the root, instead passing through another intermediate node.

Observations

It looks like the path always passes through some intermediate node and ends at leaf nodes. This makes sense because we want to maximize the diameter of the tree – we want to go as far apart from the intermediate node – we land at leaf nodes, since they are the farthest away, literally at the bottom of the tree.

While we are at it, let’s try to find the answers for the above case.

This makes sense from our previous considerations. The answer for the node is 3, since right = 1 and left = 2. What about root as an intermediate?

Here we are stuck. We can only pick one of the branches of the tree. Which one do we pick? We pick left = 2 since that is going to maximize the diameter for the root, instead of right = 1. We then pass on max(left, right)+1 since there is the additional edge we want to consider.

Code for Diameter of Binary Tree

# 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:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node: return 0
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            nonlocal ans
            ans = max(ans, left + right)
            return max(left, right) + 1
        
        ans = 0
        dfs(root)
        return ans

Thanks for reading!

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.