Problem statement

You are given the root of a binary tree in which every node holds a value from 0 to 25, standing for the letters 'a' to 'z'.

Every path from a leaf up to the root spells a string, starting with the leaf's letter and ending with the root's. Return the lexicographically smallest of these strings.

As usual, a string that is a proper prefix of another is the smaller one: "ab" comes before "aba". A leaf is a node with no children.

Example 1

Input: root = [0,1,2,3,4,3,4]
Output: "dba"
Explanation: The four leaf-to-root strings are "dba", "eba", "dca" and "eca"; the smallest is "dba".

Example 2

Input: root = [25,1,3,1,3,0,2]
Output: "adz"
Explanation: Reading up from the leaf 0 (a) through 3 (d) to the root 25 (z) gives "adz", smaller than "bbz", "dbz" and "cdz".

Example 3

Input: root = [2,2,1,null,1,0,null,0]
Output: "abc"
Explanation: The leaf on the left side spells "abcc" (0 → 1 → 2 → 2) and the one on the right side "abc" (0 → 1 → 2). "abc" is a prefix of "abcc", so it is the smaller.

Constraints

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

Hints for Smallest String Starting From Leaf

1. Hint 1

   Every candidate starts at a leaf, so you need the whole path from the root down to each leaf.

2. Hint 2

   Walk down with a DFS, keeping the letters of the current root-to-node path. At a leaf, reverse the path to get its string and compare it with the best so far.

3. Hint 3

   Merging bottom-up — keeping only the smaller of the two children's answers and appending the node's letter — fails: a string that loses below can win once the letters above are added ("a" beats "aba", but "abz" loses to "ababz"). Compare complete strings.

How to solve Smallest String Starting From Leaf

There is one candidate per leaf, read from the leaf up. A DFS that carries the root-to-node path builds each candidate when it reaches a leaf, and the minimum over all leaves is the answer.

Approach

1. DFS from the root, appending each node's letter to a path buffer on the way down and removing it on the way back.
2. At a leaf, form the string reverse(path) — leaf first, root last.
3. Keep it if it is smaller than the best string found so far (or if it is the first one).
4. Return the best string after the DFS.

Why it works

Every leaf-to-root string is generated exactly once, and the comparison keeps the smallest. Comparing whole strings sidesteps the trap in local choices: two subtrees can start with the same letters near the leaves, and which one wins depends on letters much higher up.

Complexity

• Time — O(n · h) — each leaf builds a string of length at most h
• Space — O(h) for the path, the recursion and the best string

Pitfalls

• Read the string from the leaf to the root, not from the root down.
• Only leaves start candidates; a node with one child is not a leaf.
• Keeping only the smaller child answer at each node gives abz for [25,1,null,0,0,1,null,null,null,0], but the answer is ababz.

Reference solution

Python

from typing import Optional

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

    def walk(node):
        nonlocal best
        if node is None:
            return
        path.append(chr(97 + node.val))
        if node.left is None and node.right is None:
            s = "".join(reversed(path))
            if best is None or s < best:
                best = s
        walk(node.left)
        walk(node.right)
        path.pop()

    walk(root)
    return best

Java

public static String smallestFromLeaf(TreeNode root) {
    String[] best = new String[1];
    walk(root, new StringBuilder(), best);
    return best[0];
}

static void walk(TreeNode node, StringBuilder path, String[] best) {
    if (node == null) return;
    path.append((char) ('a' + node.val));
    if (node.left == null && node.right == null) {
        String s = new StringBuilder(path).reverse().toString();
        if (best[0] == null || s.compareTo(best[0]) < 0) best[0] = s;
    }
    walk(node.left, path, best);
    walk(node.right, path, best);
    path.setLength(path.length() - 1);
}

C++

void leafWalk(TreeNode* node, string& path, string& best, bool& have);

string smallestFromLeaf(TreeNode* root) {
    string path, best;
    bool have = false;
    leafWalk(root, path, best, have);
    return best;
}

void leafWalk(TreeNode* node, string& path, string& best, bool& have) {
    if (!node) return;
    path.push_back((char) ('a' + node->val));
    if (!node->left && !node->right) {
        string s(path.rbegin(), path.rend());
        if (!have || s < best) { best = s; have = true; }
    }
    leafWalk(node->left, path, best, have);
    leafWalk(node->right, path, best, have);
    path.pop_back();
}

JavaScript

var smallestFromLeaf = function(root) {
    var best = null, path = [];
    var walk = function(node) {
        if (node === null) return;
        path.push(String.fromCharCode(97 + node.val));
        if (node.left === null && node.right === null) {
            var s = path.slice().reverse().join("");
            if (best === null || s < best) best = s;
        }
        walk(node.left);
        walk(node.right);
        path.pop();
    };
    walk(root);
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Design a Food Rating System Medium
• Design Bitset Medium
• Iterator for Combination Medium
• Time Based Key-Value Store Medium
• Map Sum Pairs Medium
• Implement Magic Dictionary Medium