Abstract / Summary

Find the lexicographically smallest string formed by characters along any root to leaf path 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 61% (300k+ submissions).

Typical patterns to solve this problem:

• Backtracking
• Binary Tree
• Depth First Search
• String
• 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 class Solution with a method smallestFromLeaf that, given the root of a binary tree whose nodes store integer values in the range 0-25, returns the lexicographically smallest string that can be formed by reading characters from a leaf node up to the root. The characters are derived by mapping each integer to a lowercase English letter (0 → 'a', 1 → 'b', …, 25 → 'z'). The algorithm performs a depth-first traversal, constructs candidate strings on the fly, and keeps track of the best (smallest) string encountered.

Key Steps

Character Mapping Helper

A small inner function translates an integer index to its corresponding character. The function adds the index to the ASCII code of 'a' and converts the result back to a character.

def abc(i):
    return chr(i + ord("a"))

This helper is used throughout the traversal to convert node values into letters.

Sentinel Initialization

Before the traversal begins, a sentinel string is created that is guaranteed to be larger than any possible leaf-to-root string. By calling abc(26), the code obtains the character '{', which follows 'z' in the ASCII table. This sentinel serves as the initial value for the variable that will hold the smallest string.

best = abc(26)  # larger than a-z

Recursive Depth-First Traversal

The core of the algorithm is the nested function deeper. It receives a node reference and the string built so far (have). The function follows these steps:

1. Base case for null nodes - If the current node is None, the function returns immediately, preventing further recursion.

   if not node:
       return

2. Prepend current character - The character representing the current node’s value is placed at the front of the accumulated string. This order ensures that the final string reads from leaf to root.

   have = abc(node.val) + have

3. Leaf detection and best-string update - When a node has no left or right children, it is a leaf. At this point the algorithm compares the newly formed string with the current best and retains the smaller one using Python’s built-in min.

   if not node.left and not node.right:
       nonlocal best
       best = min(best, have)
       return

4. Recursive descent - If the node is not a leaf, the function recurses on the left child followed by the right child, passing along the updated string.

   deeper(node.left, have)
   deeper(node.right, have)

The recursion builds strings incrementally as it walks down each root-to-leaf path, guaranteeing that every possible leaf-originated string is examined.

Invocation and Result Return

After defining deeper, the method initiates the traversal with an empty string and the supplied root node. Once the recursion completes, the variable best holds the smallest lexicographic string, which is then returned.

deeper(root, "")
return best

Edge Cases Handled

The implementation gracefully handles several boundary conditions:

• Empty tree - If root is None, the initial call to deeper immediately returns without modifying best. The method then returns the sentinel '{'. This behavior provides a deterministic output for an empty input, avoiding exceptions.

• Single-node tree - When the tree consists of only the root, that node is also a leaf. The algorithm constructs a one-character string from the root’s value and compares it with the sentinel, resulting in the correct single-letter answer.

• All possible leaf depths - Because the traversal explores both left and right subtrees recursively, it correctly processes trees where leaves appear at varying depths, ensuring that no leaf path is omitted.

• Maximum character value - The mapping function abc works for any integer from 0 to 25. The sentinel uses i = 26, which yields '{'. This choice guarantees that any legitimate leaf string (composed only of 'a'-'z') will be lexicographically smaller than the sentinel, simplifying the initialization logic.

Performance Optimizations Observed

The code incorporates a few subtle choices that contribute to efficient execution:

• In-place string building with prepend - By constructing the candidate string as abc(node.val) + have, the algorithm avoids the need for additional data structures such as lists or stacks to reverse the order later. Each recursive call carries the exact string needed for comparison, eliminating post-processing steps.

• Early leaf comparison - The check for leaf nodes occurs immediately after updating have. This allows the algorithm to update best without descending further, preventing unnecessary recursive calls beyond leaf nodes.

• Use of built-in min - Leveraging Python’s native min function for string comparison is faster than implementing a custom comparison routine, as it is highly optimized in the interpreter.

• Nonlocal variable for best - Declaring best as nonlocal inside deeper avoids passing it as a parameter on each recursive call, reducing the overhead of argument handling and keeping the recursion signature minimal.

These design decisions keep the runtime overhead low while maintaining clear and concise logic.

Imagine a tree that grows upside down with little numbers hidden inside each branch. This code is like a game of hide and seek that finds a secret word made of letters. Every number in the tree corresponds to a letter, where zero is a, one is b, and so on.

The code starts at the very top of the tree, which is called the root. It walks down all the different paths until it reaches the end of a branch, which is called a leaf. As it walks, it keeps track of the letters it finds along the way. Every time it gets to the end of a path, it looks at the word it spelled.

Because there are many paths to choose from, it keeps a special list of all the words it finds. It compares them to find the one that would come first in a dictionary, just like finding which word starts with an earlier letter in the alphabet. Once it reaches the bottom of every possible path in the tree, the word that comes first alphabetically is the one it settles on. It is a very busy little worker that explores every single corner of the tree to make sure it picked the best word of all.

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++			Java
	leetcode.ca	C++	Python		Java			Go
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fartem					Ruby
	fsq	C++
	Garvit244		Python
	haoel	C++
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM						C#
	varunu28				Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
Garvit244	Python
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java

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