# 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!

### Recommended Posts

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022