Smallest String Starting From Leaf

Problem

For each root-to-leaf path, interpret digits as characters (0='a', 25='z'). Return the lexicographically smallest string read from leaf to root.

Key insight: DFS to leaves, build reversed string, compare.

Solutions

// C++
string smallest = "";
void dfs(TreeNode* node, string path) {
    if (!node) return;
    path = char('a' + node->val) + path;
    if (!node->left && !node->right) {
        if (smallest.empty() || path < smallest) smallest = path;
        return;
    }
    dfs(node->left, path);
    dfs(node->right, path);
}
string smallestFromLeaf(TreeNode* root) {
    dfs(root, "");
    return smallest;
}

// Java
String smallest = "";
public String smallestFromLeaf(TreeNode root) {
    dfs(root, new StringBuilder());
    return smallest;
}
void dfs(TreeNode node, StringBuilder path) {
    if (node == null) return;
    path.insert(0, (char)('a' + node.val));
    if (node.left == null && node.right == null) {
        String s = path.toString();
        if (smallest.isEmpty() || s.compareTo(smallest) < 0) smallest = s;
    }
    dfs(node.left, path);
    dfs(node.right, path);
    path.deleteCharAt(0);
}

// JavaScript
function smallestFromLeaf(root) {
    let smallest = null;
    function dfs(node, path) {
        if (!node) return;
        const ch = String.fromCharCode(97 + node.val);
        path = ch + path;
        if (!node.left && !node.right) {
            if (smallest === null || path < smallest) smallest = path;
        }
        dfs(node.left, path);
        dfs(node.right, path);
    }
    dfs(root, '');
    return smallest;
}

# Python
def smallestFromLeaf(root):
    smallest = [None]
    def dfs(node, path):
        if not node:
            return
        path = chr(ord('a') + node.val) + path
        if not node.left and not node.right:
            if smallest[0] is None or path < smallest[0]:
                smallest[0] = path
        dfs(node.left, path)
        dfs(node.right, path)
    dfs(root, '')
    return smallest[0]

Complexity

Time: O(n * h) due to string prepend
Space: O(h)