Smallest String Starting From Leaf

Given the root of a binary tree where each node has a value from 0 to 25 (mapping to the letters 'a' through 'z'), return the lexicographically smallest string that starts at a leaf and ends at the root.

This is LeetCode 988: Smallest String Starting From Leaf. The string is formed by reading values from a leaf node upward to the root. Each node's integer value maps to a character: 0 becomes 'a', 1 becomes 'b', and so on up to 25 for 'z'.

Example: A tree with root = [0, 1, 2, 3, 4, null, 0] has three leaf-to-root paths. The letters are a=0, b=1, c=2, d=3, e=4. The paths produce "dba", "eba", and "aca". The answer is "aca".

Why this problem matters

This problem combines two skills that come up repeatedly in tree questions: building a path during DFS, and comparing accumulated results at the leaves. It is a close relative of Binary Tree Paths, but with a twist. Instead of collecting all paths, you only keep the best one. And instead of reading root-to-leaf, you read leaf-to-root. That reversal is where most of the difficulty lives.

Brute force approach

The direct approach is to collect every leaf-to-root path as a string, then pick the smallest.

def smallestFromLeaf(root):
    results = []
    def dfs(node, path):
        if not node:
            return
        path.append(chr(node.val + ord('a')))
        if not node.left and not node.right:
            results.append(''.join(reversed(path)))
        dfs(node.left, path)
        dfs(node.right, path)
        path.pop()
    dfs(root, [])
    return min(results)

This works but stores every path. For a tree with many leaves, you are keeping strings you will never use. You can do better by tracking the current best as you go.

Key insight

You do not need to store all paths. Carry a list of characters downward during DFS. When you reach a leaf, reverse the list to form the leaf-to-root string and compare it against the best string found so far. If the new string is smaller, update the best.

The critical detail is the reversal. You build the path top-down (root to leaf) because that is the natural direction of DFS. But the problem asks for the string bottom-up (leaf to root). So at each leaf, you reverse the path to get the correct string, then compare.

Walking through step by step

Let's trace through the tree [0, 1, 2, 3, 4, null, 0] (letters: a, b, c, d, e, a) and watch how the DFS discovers and compares leaf-to-root strings.

The winning path goes through the right subtree. Even though "dba" was found first, "aca" is lexicographically smaller because 'a' comes before 'd'. You cannot know the winner until you have checked every leaf.

The solution

def smallestFromLeaf(root):
    best = None
    def dfs(node, path):
        nonlocal best
        if not node:
            return
        path.append(chr(node.val + ord('a')))
        if not node.left and not node.right:
            candidate = ''.join(reversed(path))
            if best is None or candidate < best:
                best = candidate
        dfs(node.left, path)
        dfs(node.right, path)
        path.pop()
    dfs(root, [])
    return best

Here is what each piece does:

• best = None tracks the smallest complete string found so far.
• path.append(chr(node.val + ord('a'))) converts the node's integer to its letter and adds it to the running path.
• The leaf check if not node.left and not node.right fires when both children are None. At that point you reverse the path to form the leaf-to-root string.
• if best is None or candidate < best updates the running minimum. Python's string comparison is lexicographic by default.
• path.pop() undoes the append when backtracking, so the path is clean for the next branch.
• dfs(root, []) starts the recursion with an empty path list.

Complexity analysis

Time is O(n * L) where n is the number of nodes and L is the height of the tree. You visit every node once (O(n)), and at each leaf you reverse and join the path, which takes O(L) time. In the worst case (skewed tree), L = n, giving O(n^2). For a balanced tree, L = log n, giving O(n log n).

Space is O(n). The path list and the recursion stack each use up to O(h) space where h is the tree height. The best string uses up to O(h) space. In the worst case h = n.

Building blocks

This problem combines two fundamental patterns:

1. Pre-order state passing with backtracking. You carry a mutable path list from parent to child as you descend. At each leaf, you use the accumulated path. After processing both children, you pop the last element to restore the path for the next branch. This is the same pattern used in Binary Tree Paths and Path Sum, but with an explicit backtrack step because you are using a shared mutable list instead of immutable string concatenation.

2. Running minimum comparison. Instead of collecting all candidates and picking the best at the end, you maintain a single best variable and update it whenever you find something smaller. This avoids storing results you will never need. The pattern appears in any problem where you want the min or max of many candidates discovered during a traversal.

Edge cases

• Single node (root is a leaf). The tree has one leaf-to-root path containing one character. Return chr(root.val + ord('a')).
• Left-skewed tree. There is exactly one leaf at the bottom. The DFS follows the chain all the way down, builds one string, and returns it.
• All nodes have the same value. Every leaf-to-root path produces the same string. The answer is that string. The length of the path does not matter when all characters are identical, but shorter paths will be lexicographically smaller (e.g., "aa" is smaller than "aaa"). The shallowest leaf wins.
• Two paths differ only at the leaf. The DFS will compare the full reversed strings. The leaf character becomes the first character of the string, so the leaf with the smaller value wins.

Common mistakes

1. Building the string root-to-leaf instead of leaf-to-root. The problem specifically asks for the string starting at the leaf. If you forget to reverse, you get the wrong answer.
2. Pruning based on partial strings. You cannot stop exploring a branch just because the current path looks worse than best. A deeper leaf might produce a shorter (and therefore smaller) string.
3. Using min() on partial path lists. Comparing lists of characters is not the same as comparing the reversed joined strings. Always form the complete string before comparing.
4. Forgetting to backtrack. If you use a shared mutable list for the path, you must call path.pop() after processing both children. Otherwise subsequent branches see leftover characters from earlier paths.

From understanding to recall

You just watched the DFS append characters going down and reverse them at each leaf to build the correct leaf-to-root string. You saw how "dba" was found first but "aca" replaced it as the best. The combination of backtracking, reversal, and running comparison makes this problem a solid test of tree traversal fundamentals.

But will you remember the reversal step under interview pressure? Will you remember to use nonlocal best in the nested function? Will you instinctively reach for backtracking with path.pop() when using a shared list?

Spaced repetition builds that recall. You type the solution from scratch at increasing intervals: after a day, then three days, then a week. Each time, you reconstruct the DFS helper, the leaf check, the reversal, and the comparison from memory. After a few rounds, the pattern becomes automatic.

Pre-order state passing with backtracking is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Binary Tree Paths - The same DFS path-building pattern, but collecting all root-to-leaf paths instead of finding the smallest leaf-to-root string
• Sum Root to Leaf Numbers - Another pre-order state passing problem where you accumulate values along root-to-leaf paths, but with numbers instead of strings
• Path Sum - The foundational pre-order state passing problem where you carry a running target downward and check a condition at leaves

CodeBricks breaks problems like Smallest String Starting From Leaf into the building blocks behind them, then uses spaced repetition to make those blocks automatic. If you want to stop re-solving the same patterns and start recognizing them on sight, give it a try.