Abstract / Summary

Find the smallest possible height of a tree after removing one node to make it a forest of equal subtrees.

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 43% (1+ million submissions).

Typical patterns to solve this problem:

• Breadth First Search
• Depth First Search
• Graph
• Topological Sort

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 solves the “minimum height trees” problem for an undirected graph that is a tree. It builds an adjacency representation, removes certain leaf nodes that can never be optimal roots, then evaluates the height of the tree when each remaining node is treated as the root. The nodes that achieve the smallest height are returned.

Building the adjacency structure

The algorithm starts by creating a dictionary where each vertex maps to a set of its neighbors.

connect = {}
for i in range(n):
    connect[i] = set()

Iterating over the edge list populates the neighbor sets in both directions, guaranteeing an undirected representation.

for e in edges:
    connect[e[0]].add(e[1])
    connect[e[1]].add(e[0])

Using a set for each adjacency list provides O(1) membership checks and prevents duplicate entries.

Pruning non-candidate leaves

A leaf is a node with exactly one neighbor. The code identifies leaves whose sole neighbor has degree greater than one; such leaves cannot be the root of a minimum-height tree because any root must be at least as deep as its farthest leaf. Those leaves are collected in a temporary list and then removed from the adjacency dictionary.

prune = []
for c in connect:
    current = connect[c]
    if len(current) == 1:
        (first,) = current
        if len(connect[first]) > 1:
            prune.append(c)
for p in prune:
    del connect[p]

By deleting these vertices early, the subsequent depth calculations avoid unnecessary recursion into branches that would never influence the optimal height.

Recursive depth calculation with memoization

The core of the height evaluation is a depth-first search that returns the longest distance from a given node to any descendant, excluding the parent to prevent backtracking. The function is decorated with @cache, which stores results for each (node, parent) pair. This memoization eliminates repeated work when the same sub-tree is explored from different starting points.

@cache
def deeper(node, parent):
    if node not in connect:
        return 1
    longest = 0
    for c in connect[node]:
        if c != parent:
            longest = max(longest, deeper(c, node))
    return longest + 1

The early return for a node that has been pruned (node not in connect) treats the missing node as a leaf with depth 1, ensuring that the recursion terminates cleanly for pruned branches.

Evaluating each candidate root

The algorithm iterates over the remaining vertices after pruning, invoking the cached depth function with the node as both the starting point and its own parent. This call yields the height of the tree when that node is considered the root.

best = 99999999
result = []
for c in connect:
    current = deeper(c, c)
    if best > current:
        best = current
        result.clear()
    if best == current:
        result.append(c)

The variables best and result track the smallest height encountered and the list of nodes that achieve it. When a new smaller height is found, the result list is cleared before the current node is added; nodes with height equal to the current best are appended.

Edge conditions addressed

The code naturally handles a single-node tree (n == 1). In that case the adjacency dictionary contains one entry with an empty neighbor set; the pruning loop does not remove it because the leaf’s neighbor does not exist, and the depth function returns 1, correctly identifying the sole node as the minimum-height root.

When the input graph is already a star (one central node connected to all others), the pruning step removes all outer leaves, leaving only the central node. The depth calculation then returns a height of 2, and the central node is returned as the unique optimal root.

If the graph contains multiple disconnected components (which violates the tree assumption), the adjacency construction still creates separate sets. The pruning step may delete leaves in each component, and the depth function will treat missing nodes as depth 1. The final loop evaluates each remaining component independently, producing a result list that contains the minimal-height roots for each component.

The recursion guard if c != parent prevents infinite loops in cyclic structures, ensuring that even if the input were not a tree, the algorithm would not get stuck traversing a cycle.

Performance optimizations observed

The use of a dictionary of sets for adjacency provides constant-time neighbor lookup and efficient removal of pruned vertices. Pruning eliminates a potentially large number of leaf nodes before any depth computation, reducing the size of the search space dramatically for trees with many peripheral leaves.

Memoization via @cache is a key optimization: each sub-tree’s height is computed once per distinct parent relationship, and subsequent calls retrieve the stored value instantly. This dramatically cuts down the number of recursive calls, especially in dense or balanced trees where many roots share large overlapping sub-trees.

Avoiding explicit parent tracking structures and instead passing the parent as a function argument keeps the recursion lightweight. The early exit for pruned nodes (if node not in connect) prevents unnecessary traversal into branches that have already been eliminated.

Overall, the combination of adjacency pruning, set-based neighbor storage, and cached depth calculations yields a solution that scales well for large trees while maintaining clear and concise logic.

Imagine you have a bunch of dots connected by strings, like a drawing of stars in the sky. Some dots are at the very ends of the strings, hanging out like little leaf tips. This code is trying to find the best spots in the middle to grab onto so that everything hangs down nicely and evenly.

First, it creates a list of all the dots and sees which other dots they are holding hands with. It draws little maps so it knows exactly how every dot is connected to its neighbors.

Because the dots at the very ends do not make good centers, the code carefully snips those end pieces away. It knows that holding onto an end leaf would make the whole shape lopsided and tall, which is not what is wanted.

Now the code plays a game of measuring. It picks up each remaining dot and pretends it is the center. It looks at all the paths spreading out from that dot and counts how long those paths are. It keeps track of the longest path it finds for each dot because that tells it how tall the shape would be if that dot were the center.

Finally, the code compares all those centers. It searches for the ones that result in the shortest longest path. These special center dots are the winners because they keep the whole shape balanced and compact, like holding a mobile perfectly so it does not tip to one side.

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

not analyzed yet

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		Java			Go	TS
	LeetcodeHelp	C++		Python		Java
	MemoryLimitExceeded	C++		Python
	Progiez	C++		Python		Java
github	aylei		Rust
	black-shadows	C++
	charles-wangkai					Java
	chenyanzhe	C++
	everthis				JS
	fengvyi	C++
	fpdjsns	C++
	haoel	C++
	JoshCrozier				JS
	linouk23	C++
	lkwq007			Python
	ruoru		Rust
	sonugiri1043	C++
	suxrobGM							C#
	trung-hn			Python
	varunu28					Java
	wisdompeak	C++
	XiaotaoGuo	C++
	yuanliu666						Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fengvyi	C++
fpdjsns	C++
haoel	C++
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
XiaotaoGuo	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