LeetCode 988 - Smallest String Starting From Leaf

LeetCode Problem 988

Difficulty: 🟡 Medium
Topics: String, Backtracking, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem gives us the root of a binary tree where every node stores an integer between 0 and 25. Each integer corresponds to a lowercase English letter:

• 0 -> 'a'
• 1 -> 'b'
• ...
• 25 -> 'z'

We need to construct strings that begin at a leaf node and move upward toward the root. Among all such leaf-to-root strings, we must return the lexicographically smallest one.

A key detail is the direction of the string. Although traversal naturally moves from the root downward, the required string is formed from leaf to root. For example, if a path from root to leaf is:

a -> b -> d

then the resulting string is:

"dba"

not "abd".

Lexicographical comparison works exactly like dictionary ordering. The first differing character determines which string is smaller. If one string is a prefix of another, the shorter string is considered smaller.

The tree can contain up to 8500 nodes, which is large enough that we should avoid unnecessary repeated string construction or storing every possible path if we can help it. However, this size is still manageable for a depth-first traversal because the height of the tree is bounded by the number of nodes.

Several edge cases are important:

• A tree with only one node. In this case, the root is also a leaf, so the answer is a single character.
• Multiple leaf paths producing strings with common prefixes. Lexicographical comparison must still work correctly.
• Deep trees where repeated string concatenation could become expensive.
• Trees where the lexicographically smallest answer is not the shortest path.
• Trees containing many repeated values, which can make comparisons subtle.

The problem guarantees that every node value is valid and that at least one node exists.

Approaches

Brute Force Approach

The most straightforward solution is to generate every leaf-to-root string and then return the lexicographically smallest one.

We can perform a depth-first traversal from the root while maintaining the current root-to-node path. Whenever we reach a leaf, we reverse the collected characters to produce the required leaf-to-root string. We then store that string in a list. After traversing the entire tree, we sort the list or repeatedly compare strings to find the smallest one.

This approach is correct because it explicitly enumerates every valid candidate string. Since the answer must be one of these strings, comparing all of them guarantees we find the correct result.

The drawback is that we may store many full strings simultaneously. In the worst case, the tree can have many leaves, and each generated string can be long. Repeated reversing and string creation also adds overhead.

Optimal Approach

The key observation is that we do not actually need to store all candidate strings. We only need the smallest one seen so far.

We can still perform a DFS traversal, but instead of collecting all results, we maintain a global best string. At each leaf:

1. Construct the current leaf-to-root string.
2. Compare it directly against the best answer seen so far.
3. Replace the answer if the new string is smaller.

This reduces memory usage because we only keep the current traversal path and the current best answer.

The DFS traversal naturally explores every root-to-leaf path exactly once, making it ideal for this problem.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N × H)	O(N × H)	Stores every leaf string before comparison
Optimal	O(N × H)	O(H)	DFS with on-the-fly lexicographical comparison

Here:

• N is the number of nodes
• H is the height of the tree

Algorithm Walkthrough

Optimal DFS Algorithm

1. Start a depth-first traversal from the root node.

We use DFS because the problem requires examining every root-to-leaf path. DFS naturally maintains the current traversal path. 2. Maintain a mutable path structure during traversal.

As we visit each node, we convert its numeric value into a character using:

chr(node.val + ord('a'))

We append this character to the current path. 3. Continue recursively into the left and right children.

The path now represents the sequence of characters from the root down to the current node. 4. When a leaf node is reached, construct the candidate string.

Since the required direction is leaf-to-root, we reverse the current path and join it into a string.

For example:

path = ['a', 'b', 'd']

becomes:

"dba"

5. Compare the candidate string against the current best answer.

If:

• no answer has been recorded yet, or
• the new string is lexicographically smaller,

then update the answer. 6. Backtrack after processing the node.

Remove the current character from the path before returning to the parent call. This ensures the path always accurately reflects the active recursion branch. 7. After DFS completes, return the stored smallest string.

Why it works

The DFS traversal visits every root-to-leaf path exactly once. Every valid answer corresponds to one such path, so no candidate string is missed. At each leaf, we generate the exact leaf-to-root string required by the problem. Because we continuously maintain the lexicographically smallest candidate encountered so far, the final stored string must be the smallest among all possible leaf-to-root strings.

Python Solution

# 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

from typing import Optional

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

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

            if not node:
                return

            path.append(chr(node.val + ord('a')))

            if not node.left and not node.right:
                candidate = ''.join(reversed(path))

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

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

            path.pop()

        dfs(root)
        return smallest

The implementation uses recursive DFS traversal. The path list stores the characters from the root to the current node. Using a list is important because repeated string concatenation inside recursion would be inefficient.

Whenever we visit a node, we append its character representation to the path. If the node is a leaf, we reverse the path to produce the required leaf-to-root ordering and compare it against the current best answer.

The variable smallest stores the best string found so far. Since Python supports direct lexicographical string comparison, we can simply use:

candidate < smallest

Backtracking is handled with path.pop(). This restores the path state before returning to the parent recursive call.

The recursion naturally explores all root-to-leaf paths while keeping the implementation concise and efficient.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func smallestFromLeaf(root *TreeNode) string {
    smallest := ""
    path := make([]byte, 0)

    var dfs func(node *TreeNode)

    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }

        path = append(path, byte('a'+node.Val))

        if node.Left == nil && node.Right == nil {
            candidateBytes := make([]byte, len(path))

            for i := 0; i < len(path); i++ {
                candidateBytes[i] = path[len(path)-1-i]
            }

            candidate := string(candidateBytes)

            if smallest == "" || candidate < smallest {
                smallest = candidate
            }
        }

        dfs(node.Left)
        dfs(node.Right)

        path = path[:len(path)-1]
    }

    dfs(root)

    return smallest
}

The Go solution follows the same DFS and backtracking strategy as the Python version.

One important difference is string construction. Since Go strings are immutable, we use a []byte slice for the traversal path. At each leaf, we manually construct the reversed candidate string.

Backtracking is implemented by shrinking the slice:

path = path[:len(path)-1]

Go also requires explicit handling of nil pointers during recursion.

Worked Examples

Example 1

Input:

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

Tree:

        a
      /   \
     b     c
    / \   / \
   d   e d   e

Leaf-to-root strings:

Leaf Path	String
d -> b -> a	"dba"
e -> b -> a	"eba"
d -> c -> a	"dca"
e -> c -> a	"eca"

Comparison process:

Candidate	Current Smallest
"dba"	"dba"
"eba"	"dba"
"dca"	"dba"
"eca"	"dba"

Final answer:

"dba"

Example 2

Input:

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

Tree:

          z
        /   \
       b     d
      / \   / \
     b   d a   c

Leaf-to-root strings:

Leaf Path	String
b -> b -> z	"bbz"
d -> b -> z	"dbz"
a -> d -> z	"adz"
c -> d -> z	"cdz"

Lexicographical comparison:

"adz" < "bbz"

Therefore the answer is:

"adz"

Example 3

Input:

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

Traversal process:

Current Path Root-to-Node	Leaf-to-Root Candidate
c -> b -> a	"abc"
c -> c -> b -> a	"abcc"

Lexicographical comparison:

"abc" < "abcc"

because "abc" is a prefix of "abcc".

Final answer:

"abc"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N × H)	Each leaf may require building a string of length up to tree height
Space	O(H)	DFS recursion stack and path storage

The DFS visits each node exactly once, contributing O(N) traversal cost. However, at every leaf we may construct a reversed string whose length can be up to the tree height H. In the worst case, many leaves exist, giving an overall complexity of O(N × H).

The auxiliary space complexity is O(H) because the recursion stack and current traversal path only store nodes along the current branch.

Test Cases

# Definition for testing
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):
        smallest = None
        path = []

        def dfs(node):
            nonlocal smallest

            if not node:
                return

            path.append(chr(node.val + ord('a')))

            if not node.left and not node.right:
                candidate = ''.join(reversed(path))

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

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

            path.pop()

        dfs(root)
        return smallest

sol = Solution()

# Example 1
root1 = TreeNode(
    0,
    TreeNode(1, TreeNode(3), TreeNode(4)),
    TreeNode(2, TreeNode(3), TreeNode(4))
)
assert sol.smallestFromLeaf(root1) == "dba"  # standard balanced tree

# Example 2
root2 = TreeNode(
    25,
    TreeNode(1, TreeNode(1), TreeNode(3)),
    TreeNode(3, TreeNode(0), TreeNode(2))
)
assert sol.smallestFromLeaf(root2) == "adz"  # smallest path from right subtree

# Example 3
root3 = TreeNode(
    2,
    TreeNode(2, None, TreeNode(1, TreeNode(0))),
    TreeNode(1, TreeNode(0))
)
assert sol.smallestFromLeaf(root3) == "abc"  # prefix comparison case

# Single node tree
root4 = TreeNode(0)
assert sol.smallestFromLeaf(root4) == "a"  # root is also leaf

# Left-skewed tree
root5 = TreeNode(2, TreeNode(1, TreeNode(0)))
assert sol.smallestFromLeaf(root5) == "abc"  # single deep path

# Right-skewed tree
root6 = TreeNode(1, None, TreeNode(0, None, TreeNode(2)))
assert sol.smallestFromLeaf(root6) == "cab"  # right-only traversal

# Multiple equal prefixes
root7 = TreeNode(
    0,
    TreeNode(1, TreeNode(0)),
    TreeNode(1, TreeNode(1))
)
assert sol.smallestFromLeaf(root7) == "aba"  # compares after shared prefix

# All same characters
root8 = TreeNode(
    0,
    TreeNode(0, TreeNode(0)),
    TreeNode(0)
)
assert sol.smallestFromLeaf(root8) == "aa"  # repeated characters

# Deep comparison where shorter string wins
root9 = TreeNode(
    2,
    TreeNode(1, TreeNode(0)),
    TreeNode(1, TreeNode(0, TreeNode(0)))
)
assert sol.smallestFromLeaf(root9) == "abc"  # shorter prefix is smaller

Test	Why
Balanced example tree	Validates standard multi-path traversal
Right subtree optimal	Ensures traversal checks all leaves
Prefix comparison	Verifies lexicographical prefix handling
Single node	Tests smallest possible input
Left-skewed tree	Tests deep recursion on one side
Right-skewed tree	Tests asymmetric structure
Shared prefixes	Ensures deeper character comparison works
Repeated characters	Handles duplicate values correctly
Shorter prefix wins	Verifies lexicographical edge rule

Edge Cases

Single Node Tree

A tree containing only one node is an important boundary condition because the root is also a leaf. A buggy implementation might assume leaf nodes always have parents or might incorrectly reverse an empty path. In this implementation, the DFS immediately identifies the root as a leaf and constructs a one-character string correctly.

Lexicographical Prefix Comparisons

Cases like "abc" versus "abcc" are subtle because the shorter string is lexicographically smaller even though all existing characters match. Implementations that compare only by length or stop comparison too early can fail here. Python and Go both use standard lexicographical string comparison, which correctly handles prefix ordering automatically.

Deep Skewed Trees

A highly unbalanced tree behaves almost like a linked list. Naive solutions that repeatedly copy strings at every recursive step can become inefficient. This implementation avoids excessive copying by maintaining a mutable path structure and only constructing strings when reaching leaves.

Multiple Identical Characters

Trees where many nodes contain the same value can create many nearly identical candidate strings. This can expose issues in comparison logic or path handling. Since the algorithm constructs exact leaf-to-root strings and compares them directly, repeated characters are handled naturally and correctly.