LeetCode 988: Smallest String Starting From Leaf

Problem Restatement

We are given the root of a binary tree.

Each node has a value from 0 to 25.

Each value maps to a lowercase English letter:

We need to return the lexicographically smallest string that starts at a leaf and ends at the root.

A leaf is a node with no children.

The number of nodes is in the range [1, 8500], and every node value is in the range [0, 25].

Input and Output

Function shape:

def smallestFromLeaf(root: Optional[TreeNode]) -> str:
    ...

Examples

Example 1:

root = [0, 1, 2, 3, 4, 3, 4]

This tree has root value 0, which maps to "a".

One leaf-to-root path is:

3 -> 1 -> 0

This becomes:

"dba"

Another leaf-to-root path is:

4 -> 1 -> 0

This becomes:

"eba"

The smallest possible string is:

"dba"

Answer:

"dba"

Example 2:

root = [25, 1, 3, 1, 3, 0, 2]

The answer is:

"adz"

Example 3:

root = [2, 2, 1, None, 1, 0, None, 0]

The answer is:

"abc"

First Thought: Build Every Leaf-to-Root String

The direct idea is to traverse every root-to-leaf path.

When we reach a leaf, reverse the path because the required string starts at the leaf and ends at the root.

Then compare that string with the best answer so far.

For example, if the current root-to-leaf path is:

["a", "b", "d"]

then the leaf-to-root string is:

"dba"

We can keep only the smallest string found so far.

Key Insight

DFS naturally explores root-to-leaf paths.

At each node, we add its character to the current path.

When we reach a leaf, the current path contains the root-to-leaf string. Since the problem wants leaf-to-root order, we reverse it before comparison.

We do not need to store every path. We only keep:

Algorithm

Use DFS with backtracking.

For each node:

1. Convert node.val to a character.
2. Append that character to path.
3. If the node is a leaf:
   • reverse path
   • build the leaf-to-root string
   • update best if this string is smaller
4. Otherwise, DFS into the left and right children.
5. Remove the current character from path before returning.

Correctness

The DFS starts at the root and explores every child edge. Therefore, it reaches every leaf in the tree.

For each leaf, path contains exactly the characters on the path from the root to that leaf. Reversing path gives exactly the string from that leaf back to the root.

The algorithm compares each leaf-to-root string with the current best string and keeps the lexicographically smaller one.

Since every valid string corresponds to exactly one leaf, and the algorithm evaluates every leaf, the final best is the lexicographically smallest valid string.

Complexity

Let n be the number of nodes and h be the height of the tree.

In the worst case, h can be n, so the worst-case time can be O(n^2) for a very skewed tree.

Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
        best = None
        path = []

        def dfs(node: Optional[TreeNode]) -> None:
            nonlocal best

            if node is None:
                return

            char = chr(ord("a") + node.val)
            path.append(char)

            if node.left is None and node.right is None:
                candidate = "".join(reversed(path))

                if best is None or candidate < best:
                    best = candidate

            dfs(node.left)
            dfs(node.right)

            path.pop()

        dfs(root)
        return best

Code Explanation

We keep the best answer found so far:

best = None

The current root-to-node path is stored in a list:

path = []

At each node, convert the integer value to a character:

char = chr(ord("a") + node.val)

Then append it to the current path:

path.append(char)

If the node is a leaf:

if node.left is None and node.right is None:

we build the leaf-to-root string:

candidate = "".join(reversed(path))

Then update the answer if needed:

if best is None or candidate < best:
    best = candidate

After exploring the node’s children, remove the current node from the path:

path.pop()

This is the backtracking step.

Testing

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    root1 = TreeNode(
        0,
        TreeNode(1, TreeNode(3), TreeNode(4)),
        TreeNode(2, TreeNode(3), TreeNode(4)),
    )
    assert s.smallestFromLeaf(root1) == "dba"

    root2 = TreeNode(
        25,
        TreeNode(1, TreeNode(1), TreeNode(3)),
        TreeNode(3, TreeNode(0), TreeNode(2)),
    )
    assert s.smallestFromLeaf(root2) == "adz"

    root3 = TreeNode(
        2,
        TreeNode(2, None, TreeNode(1, TreeNode(0))),
        TreeNode(1, TreeNode(0), None),
    )
    assert s.smallestFromLeaf(root3) == "abc"

    root4 = TreeNode(0)
    assert s.smallestFromLeaf(root4) == "a"

    print("all tests passed")

run_tests()