Smallest String Starting From Leaf
Problem
You are given the root of a binary tree where each node has a value in the range 0 to 25 representing the letters 'a' to 'z'. Find the lexicographically smallest string that starts at a leaf of this tree and ends at the root. A leaf is a node with no children. The string is built by reading node letters from the leaf up to the root.
root = [0,1,2,3,4,3,4]"dba"def smallest_from_leaf(root):
best = [None]
def dfs(node, suffix):
if not node:
return
suffix = chr(ord('a') + node.val) + suffix
if not node.left and not node.right:
if best[0] is None or suffix < best[0]:
best[0] = suffix
return
dfs(node.left, suffix)
dfs(node.right, suffix)
dfs(root, "")
return best[0]function smallestFromLeaf(root) {
let best = null;
function dfs(node, suffix) {
if (!node) return;
suffix = String.fromCharCode(97 + node.val) + suffix;
if (!node.left && !node.right) {
if (best === null || suffix < best) best = suffix;
return;
}
dfs(node.left, suffix);
dfs(node.right, suffix);
}
dfs(root, "");
return best;
}class Solution {
String best = null;
public String smallestFromLeaf(TreeNode root) {
dfs(root, "");
return best;
}
private void dfs(TreeNode node, String suffix) {
if (node == null) return;
suffix = (char) ('a' + node.val) + suffix;
if (node.left == null && node.right == null) {
if (best == null || suffix.compareTo(best) < 0) best = suffix;
return;
}
dfs(node.left, suffix);
dfs(node.right, suffix);
}
}class Solution {
public:
string best = "";
bool has = false;
string smallestFromLeaf(TreeNode* root) {
dfs(root, "");
return best;
}
void dfs(TreeNode* node, string suffix) {
if (!node) return;
suffix = string(1, 'a' + node->val) + suffix;
if (!node->left && !node->right) {
if (!has || suffix < best) { best = suffix; has = true; }
return;
}
dfs(node->left, suffix);
dfs(node->right, suffix);
}
};Explanation
Each leaf-to-root path spells a word, and we want the lexicographically smallest one. Since strings are read leaf → root but we naturally walk root → leaf, the neat trick is to prepend each node's letter as we go down.
The DFS carries a suffix string. At each node we do suffix = letter(node.val) + suffix, putting the current letter in front — so by the time we reach a leaf, suffix already reads correctly from that leaf up to the root.
When we hit a leaf (no children), we compare the finished string against the best one seen so far and keep whichever is smaller. We explore every leaf this way, updating best as needed.
Example: tree [0, 1, 2, 3, 4, 3, 4] (values map 0='a', etc.). The four leaf-to-root strings are "dba", "eba", "dca", "eca". Comparing them, "dba" is the smallest, so that's the answer.
The prepend keeps the partial string oriented the right way at every step, and a simple running best means one DFS pass finds the winner.