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.
- 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.
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!
January 24, 2022