Abstract / Summary

Find the shortest distance from the root to any leaf node 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 53% (3+ million submissions).

Typical patterns to solve this problem:

• Binary Tree
• Breadth First Search
• 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 minimum depth of a binary tree using a straightforward recursive strategy. The function minDepth receives the root node of a tree and returns the length of the shortest path from the root down to the nearest leaf node. The algorithm distinguishes between empty sub-trees, leaf nodes, and internal nodes with one or two children, applying recursion only where necessary. This design ensures that each node contributes exactly once to the final depth calculation.

Key Steps

The first step checks for an empty tree. If the input root is None, the function immediately returns 0, indicating that there is no depth to measure.

if not root:
    return 0

The next condition identifies a leaf node-both left and right children are absent. In this case the depth is 1, representing the leaf itself.

if not root.left and not root.right:
    return 1

When the node has only a right child, the algorithm bypasses the left side entirely and recurses on the right subtree, adding 1 for the current node.

if not root.left:
    return 1 + self.minDepth(root.right)

Similarly, when only a left child exists, recursion proceeds exclusively on the left subtree.

if not root.right:
    return 1 + self.minDepth(root.left)

If both children are present, the function computes the minimum depth of each subtree, adds 1 for the current node, and returns the smaller of the two results.

return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

These conditional branches collectively ensure that the recursion explores only the necessary paths to determine the shortest leaf distance.

Edge Cases Handled

The implementation explicitly addresses several edge conditions:

• An entirely empty tree (root is None) yields a depth of 0. This prevents a NoneType error when the function is called with no nodes.
• A solitary node without children is recognized as a leaf, returning a depth of 1. This case avoids unnecessary recursive calls.
• Nodes with a single child are treated specially; the algorithm does not attempt to compute the minimum of a missing subtree, which would incorrectly treat a non-existent path as having depth 0. By directly recursing on the existing child, the code correctly propagates the depth through asymmetric branches.
• The final min operation is only reached when both subtrees exist, guaranteeing that the comparison is between valid integer depths.

These checks collectively ensure that the function behaves correctly across the full spectrum of binary tree shapes, from completely balanced to highly skewed structures.

Performance Optimizations

The recursive design incorporates early returns for cases where one side of a node is absent. By handling the single-child scenarios with dedicated if statements, the algorithm avoids evaluating min on a None subtree, which would otherwise introduce unnecessary recursive overhead. This selective recursion reduces the number of function calls, especially in trees that are heavily unbalanced, because each node with a missing child triggers only one recursive descent instead of two.

Additionally, the base cases (root is None and leaf detection) terminate recursion as soon as possible, preventing deeper traversal once the minimal depth path has been identified. The combination of these early exits and targeted recursion contributes to an efficient traversal that visits each node at most once, delivering a concise and performant solution.

Imagine a tree made of boxes instead of branches. Each box can have two smaller boxes attached to it. The goal is to walk from the very top box down to a box that has no others attached underneath it, while trying to pick the shortest path.

First, check if the box is empty. If there is no box at all, then the path has no length.

Next, look at the box to see if it is a leaf, which means it has no smaller boxes attached to its left or right sides. If it stands all alone, that is the end of the path and the count is one.

If the box only has one side with another box attached, keep walking down that side. Add one to the count for the box you are currently standing on, then keep counting how many more boxes are underneath until you reach the end.

If the box has attachments on both the left and the right sides, check both paths. See which side leads to the end faster by counting the boxes. Pick the smaller number of boxes from those two paths and add one for the box you are holding.

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++	Python					Java				TS
	WalkCCC	C++	Python					Java
	leetcode.ca	C++	Python	Rust		C	JS	Java		Go		TS
	LeetcodeHelp	C++	Python					Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python					Java
github	AdelDaniel										Dart
	aylei			Rust
	begeekmyfriend					C
	BigEggStudy				C#
	black-shadows		Python
	bujosa			Rust
	charles-wangkai							Java
	chenyanzhe	C++
	DimitrisJim					C
	everthis						JS
	fartem								Ruby
	fengvyi	C++
	gaosq0604		Python
	Garvit244		Python
	halfrost									Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx					C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	MacJim	C++
	qiyuangong		Python
	ruoru			Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	trung-hn		Python
	vthwang							Java
	XiaotaoGuo	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, Go, Java, JavaScript, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
AdelDaniel	Dart
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	Python, Python
bujosa	Rust
charles-wangkai	Java
chenyanzhe	C++
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fengvyi	C++
gaosq0604	Python
Garvit244	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
MacJim	C++
qiyuangong	Python
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
vthwang	Java
XiaotaoGuo	C++
YuriSpiridonov	Python
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