Abstract / Summary

Find the second smallest value in a binary tree or return the smallest if it does not exist

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 45% (400k+ 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 defines a Solution class with a method findSecondMinimumValue that receives the root of a binary tree and returns the second smallest value among the leaf nodes. If the tree does not contain at least two distinct leaf values, the method returns -1. The algorithm traverses the tree recursively, gathers unique leaf values in a set, and then extracts the required result from that set.

Key Steps

The method begins by creating an empty set that will hold the distinct values of leaf nodes.

result = set()

A nested helper function named deeper is declared to perform a depth-first traversal. The function first checks whether the current node is None and returns immediately if so, ensuring that the recursion terminates correctly at the end of each branch.

def deeper(node):
    if not node:
        return

Inside the helper, the code distinguishes between internal nodes and leaves by testing the presence of both left and right children. When both children exist, the function recurses on each child, continuing the traversal deeper into the tree.

if node.left and node.right:
    deeper(node.left)
    deeper(node.right)

If the node lacks either child, it is treated as a leaf. The leaf’s value is added to the result set. The nonlocal declaration allows the nested function to modify the result variable defined in the enclosing scope.

else:
    nonlocal result
    result.add(node.val)

After the entire tree has been visited by invoking deeper(root), the method evaluates whether the set contains fewer than two distinct values. In that situation, there is no second minimum, and the method returns -1.

if len(result) < 2:
    return -1

When at least two unique leaf values are present, the smallest value is removed from the set, and the new minimum (which corresponds to the second smallest original value) is returned.

result.discard(min(result))
return min(result)

Edge Cases Handled

The algorithm gracefully handles an empty tree because the initial call to deeper receives None, causing an immediate return and leaving the result set empty. Consequently, the length check triggers the -1 return path.

When the tree consists of a single node, that node is considered a leaf, its value is added to the set, and the length check again leads to -1 because only one distinct leaf value exists.

If all leaf nodes share the same value, the set will contain a single element despite multiple leaves. The length condition detects this and returns -1, correctly indicating the absence of a distinct second minimum.

The code also works when the tree contains a mixture of internal nodes and leaves, regardless of the depth of the leaves, because the recursive traversal explores every branch until a leaf is reached.

Performance Optimizations

Using a Python set to store leaf values provides constant-time insertion and membership checks, which keeps the collection of unique values efficient even for large trees.

The recursion avoids unnecessary processing by returning early for None nodes, preventing further function calls on absent children.

The nonlocal keyword eliminates the need for a global variable or passing the set as an argument on each recursive call, reducing overhead associated with argument handling.

Finally, the approach of discarding the smallest element and then calling min a second time leverages the set’s internal hashing structure to locate the minimum quickly without sorting the entire collection. This yields a fast extraction of the second smallest value once the traversal is complete.

Imagine a big family tree made of numbers. At the very top, there is a special number that is the smallest one in the whole group. The goal is to find the second smallest number hiding somewhere in the branches.

To do this, the computer starts at the top and goes down every single branch until it reaches the very ends, which are called leaves. Every time it finds a leaf, it remembers the number written on it. Because some numbers might be the same, the computer puts them into a special box that only keeps one of each kind.

After the computer has visited every endpoint and collected all the different numbers into the box, it empties them out. First, it finds the smallest number and whispers it away so it disappears. Now, the smallest number left in the box is actually the second smallest one from the whole tree. The computer points to that final number as the answer.

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
	leetcode.ca	C++	Java	Python		JS			Go
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai		Java
	everthis					JS
	fartem							Ruby
	fengvyi	C++
	haoel			Python
	JoshCrozier					JS
	keineahnung2345	C++
	lkwq007			Python
	qiyuangong		Java
	ruoru						Rust
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	varunu28		Java
	vthwang		Java
	YuriSpiridonov			Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, JavaScript, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
haoel	Python
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
qiyuangong	Java
ruoru	Rust
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vthwang	Java
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