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.

video solution for Diameter of Binary Tree

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.

diameter of binary tree marked
diameter of binary tree marked

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.

An example of binary tree having multiple intermediate nodes
An example of binary tree having multiple intermediate nodes

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

diameter of the binary tree marked
diameter of the binary tree marked

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?

 finding the diameter of the binary tree passing through the root
finding the diameter of the binary tree passing through the root

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.

 getting the diameter of the binary tree passing through the root
getting the diameter of the binary tree passing through the root

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!

    Leave a Reply

    Your email address will not be published. Required fields are marked *