Abstract / Summary

Find the longest path between any two nodes in a binary tree.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 66% (4+ million submissions).

Typical patterns to solve this problem:

• Binary Tree
• Depth First Search
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes the diameter of a binary tree - the length of the longest path between any two nodes, measured in edges. The solution follows a depth-first strategy, traversing the tree once while maintaining a global maximum that captures the best diameter discovered so far. The core logic resides in a nested helper function that returns the depth of the subtree rooted at a given node and updates the running diameter during the unwind phase of recursion.

Core Logic

Initialization

At the start of the public method, a mutable field self.result is created and set to zero. This field holds the maximum sum of left- and right-depths encountered during the traversal, which directly corresponds to the diameter measured in edges.

self.result = 0

Recursive Depth Computation

The nested function deeper receives a node and calculates the longest distance from that node down to any leaf. Two local variables, l and r, are initialized to zero, representing the depths of the left and right subtrees respectively. The function checks for the existence of a left child; if present, it recurses on that child, adds one to account for the edge to the child, and stores the result in l. An analogous block handles the right child, storing its depth in r.

def deeper(node):
    l = r = 0
    if node.left:
        l = 1 + deeper(node.left)
    if node.right:
        r = 1 + deeper(node.right)

Diameter Update

After obtaining the depths of both subtrees, the function updates self.result with the larger of its current value and the sum l + r. The sum represents the length of a path that passes through the current node, connecting the deepest leaf in the left subtree to the deepest leaf in the right subtree. By taking the maximum across all nodes, the algorithm captures the overall tree diameter.

    self.result = max(self.result, l + r)

Return Value

The helper returns the greater of the two subtree depths, max(l, r). This value is the depth of the subtree rooted at the current node and is used by the parent call to compute its own left or right depth.

    return max(l, r)

Invocation and Result

The recursion is initiated with the original root node. Once the entire tree has been processed, self.result contains the diameter, which the method returns.

deeper(root)
return self.result

Edge Cases Handled

When the input tree is empty (root is None), the nested function is called with None. Since the function accesses node.left and node.right only after confirming the node’s existence, the call effectively performs no work, leaving self.result at its initial value of zero. This correctly reflects that an empty tree has a diameter of zero.

For a tree consisting of a single node, both node.left and node.right are absent, so l and r remain zero. The diameter update computes max(0, 0 + 0), preserving the zero result, which matches the definition that a solitary node yields a diameter of zero edges.

In highly unbalanced (skewed) trees where all nodes lie on one side, the recursion proceeds down the single chain, accumulating a depth count while the opposite side depth stays zero. The diameter update at each node evaluates l + r where one component is zero, ultimately producing a diameter equal to the length of the chain, which is the correct longest path.

Performance Optimizations

The algorithm achieves its efficiency by performing a single post-order traversal. Each node is visited exactly once, and the depth information required for the diameter calculation is produced during the same pass, eliminating the need for separate traversals or auxiliary data structures.

Storing the intermediate maximum in an instance attribute (self.result) avoids passing the current best diameter through recursive parameters, reducing call-stack overhead and keeping the function signatures minimal.

The use of local variables l and r for depth accumulation ensures that the recursion does not allocate additional objects beyond the necessary integer values, contributing to low memory churn during execution.

Imagine a tree that grows upside down, starting from a single point at the very top. This code is designed to find the longest path that stretches from one side of the tree all the way over to the other side.

The computer starts at the top and walks down every single branch to see how deep they go. As it travels, it keeps track of the longest paths it finds along the way. When the computer visits a spot, it looks at the branch on the left and the branch on the right to see which one is longer. It adds the lengths of these two branches together to see if this secret path is the longest one discovered so far.

Think of it like measuring how wide a spider web is by checking every intersection. The code keeps climbing deeper and deeper into the tree until it reaches the very ends of the branches. By the time it finishes looking at every single connection, the widest path is clearly recorded.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java		Python								TS
	WalkCCC	C++	Java		Python
	leetcode.ca	C++	Java	C#	Python	Rust	JS	C			Go		TS
	LeetcodeHelp	C++	Java		Python
	MemoryLimitExceeded	C++			Python
	Progiez	C++	Java		Python
github	AdelDaniel											Dart
	begeekmyfriend							C
	BigEggStudy			C#
	black-shadows	C++
	bujosa					Rust
	chandansgowda				Python
	charles-wangkai		Java
	everthis						JS
	fartem								Ruby
	FelixFan1122			C#
	fengvyi	C++
	fsq				Python
	gouthampradhan		Java
	halfrost										Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007				Python
	qiyuangong		Java
	ruoru					Rust
	shreymehul			C#
	sonugiri1043	C++
	suxrobGM			C#
	varunu28		Java
	vli02							C
	vthwang		Java
	wisdompeak	C++
	yuanliu666									Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, C#, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
AdelDaniel	Dart
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
chandansgowda	Python
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fsq	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
qiyuangong	Java
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
yuanliu666	Kotlin
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality