Smallest String Starting From Leaf — LeetCode 988 DFS Pattern

Problem Statement#

You are given the root of a binary tree where each node has a value in [0, 25] representing letters a through z. Find the lexicographically smallest string that starts at a leaf and ends at the root.

Constraints:

• The number of nodes in the tree is in the range [1, 8500]
• 0 <= Node.val <= 25

Input:  root = [0,1,2,3,4,3,4]
Output: "dba"

Input:  root = [25,1,3,1,3,0,2]
Output: "adz"

Why This Problem Matters#

LeetCode 988 — Smallest String Starting From Leaf — appears at Amazon, Google, Apple, and Bloomberg as a DFS-with-path-state question. It tests two skills at once: navigating a binary tree to every leaf, and comparing strings lexicographically while remembering that "shorter is smaller" only when one string is a prefix of the other.

The phrase "starting from a leaf" inverts the usual root-to-leaf path — candidates either prepend characters as they recurse or reverse the path at each leaf. Both work, but choosing the cleaner one shows judgment.

This is a fan-favorite Amazon onsite question because it stresses path tracking, lexicographic ordering, and edge-case handling — all common in real-world ranking and trie-based search systems.

The Core Insight#

Build the path top-down using chr(ord('a') + node.val) and prepend the new character at each step (or push to a list and reverse at the leaf). At each leaf, compare the candidate string against the current best and keep the smaller. Lexicographic comparison handles the prefix tie-breaker correctly: "ab" < "aba".

A cleaner implementation prepends to avoid reversing: the path string at any node is chr(node) + path_from_parent.

Visual Dry Run#

Tree [0, 1, 2, 3, 4, 3, 4] with values mapping 0->a, 1->b, 2->c, 3->d, 4->e:

Lex smallest: dba.

Solution (Optimal)#

from typing import Optional
 
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 = ['~']  # any char larger than 'z'
 
        def dfs(node: Optional[TreeNode], suffix: str) -> None:
            if node is None:
                return
            current = chr(ord('a') + node.val) + suffix
            if node.left is None and node.right is None:
                if current < best[0]:
                    best[0] = current
                return
            dfs(node.left, current)
            dfs(node.right, current)
 
        dfs(root, "")
        return best[0]

var smallestFromLeaf = function(root) {
    let best = '~';
 
    const dfs = (node, suffix) => {
        if (!node) return;
        const current = String.fromCharCode(97 + node.val) + suffix;
        if (!node.left && !node.right) {
            if (current < best) best = current;
            return;
        }
        dfs(node.left, current);
        dfs(node.right, current);
    };
 
    dfs(root, '');
    return best;
};

Time: O(n * h) — each leaf builds a string of length O(h), and string comparison is also O(h). Space: O(h) — recursion stack and path string.

Common Mistakes#

• Comparing only the first differing character forgetting the prefix rule: "ab" < "aba" because shorter wins on tie.
• Building the path as root-to-leaf and forgetting to reverse before comparison.
• Using a global mutable string in languages where strings are immutable: each + creates a new string. With n <= 8500 and h <= n, this is acceptable but not optimal — for tighter time, use a list of chars and slice.
• Initializing best = "" and then "smaller than" returns the empty string forever. Use a sentinel like "~" (ASCII 126).
• Recursing through null children without skipping in the leaf check, falsely treating "single child" nodes as leaves.

Interview Tips#

• Define "leaf" precisely: both children are null.
• Mention the prefix rule for lex comparison.
• Walk through one branch end-to-end on the whiteboard.
• If asked for optimization, propose pruning: skip a branch when its current prefix is already worse than the best.

Follow-up Questions#

• "What if values were lowercase letters as strings, not 0-25 integers?" — Use the character directly.
• "Find the largest leaf-to-root string instead" — Flip the comparator and initial sentinel.
• "Return the leaf node, not the string" — Track the corresponding leaf alongside best.
• "Handle ties: return all leaf-to-root strings tied for smallest" — Maintain a list of candidates.
• "Stream of leaves: return current best at any time" — Maintain a running pointer, update on each new leaf.

Key Takeaways#

• LeetCode 988 Smallest String Starting From Leaf is solved via DFS that builds the leaf-to-root suffix and compares at each leaf.
• Prepending the new character avoids reversing the path at every leaf.
• Time is O(n * h); space is O(h) for recursion plus path.
• Initialize the running best to a sentinel larger than any letter (e.g., ~).
• Lexicographic comparison naturally handles the "shorter wins on prefix" rule.
• Common at Amazon, Google, and Apple as a path-DFS interview question.
• The same template solves LC 257 Binary Tree Paths and LC 129 Sum Root to Leaf Numbers with cosmetic changes.