Diameter of a binary tree

Link: https://leetcode.com/problems/diameter-of-binary-tree/

Solution:

Topics: DFS

Intuition
The key insight for this problem is understanding that we should always bubble up the longest path, but before doing that we maximize the longest path from the right + the longest path from the left! This ensures that our diameter can pass through any node.

Note: This is a bit different from most recursive problems in the sense that we can’t pass the diameter up the call-stack, we can only evaluate it momentarily at each node.

Implementation

def diameter(root)
	diameter = 0
	def dfs(node):
		if node is None:
			return 0
		left = dfs(node.left)
		right = dfs(node.right)
 
		nonlocal diameter
		diameter = max(diameter, left+right)
		return max(left, right) + 1
		
	dfs(root)
	return diameter
 
#time: o(n)
#memory: o(n)

Visual

Review 1
Nice problem. This technique is pretty common in path-finding tree problems where the best path may not pass through the root.

Same technique: Maximum path sum

review