Missing undo step on backtrack
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.
Move from brute-force thinking to an efficient approach using backtracking strategy.
You are given the root of a binary tree where each node has a value in the range [0, 25] representing the letters 'a' to 'z'.
Return the lexicographically smallest string that starts at a leaf of this tree and ends at the root.
As a reminder, any shorter prefix of a string is lexicographically smaller.
"ab" is lexicographically smaller than "aba".A leaf of a node is a node that has no children.
Example 1:
Input: root = [0,1,2,3,4,3,4] Output: "dba"
Example 2:
Input: root = [25,1,3,1,3,0,2] Output: "adz"
Example 3:
Input: root = [2,2,1,null,1,0,null,0] Output: "abc"
Constraints:
[1, 8500].0 <= Node.val <= 25Problem summary: You are given the root of a binary tree where each node has a value in the range [0, 25] representing the letters 'a' to 'z'. Return the lexicographically smallest string that starts at a leaf of this tree and ends at the root. As a reminder, any shorter prefix of a string is lexicographically smaller. For example, "ab" is lexicographically smaller than "aba". A leaf of a node is a node that has no children.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Backtracking · Tree
[0,1,2,3,4,3,4]
[25,1,3,1,3,0,2]
[2,2,1,null,1,0,null,0]
sum-root-to-leaf-numbers)binary-tree-paths)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #988: Smallest String Starting From Leaf
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private StringBuilder path;
private String ans;
public String smallestFromLeaf(TreeNode root) {
path = new StringBuilder();
ans = String.valueOf((char) ('z' + 1));
dfs(root, path);
return ans;
}
private void dfs(TreeNode root, StringBuilder path) {
if (root != null) {
path.append((char) ('a' + root.val));
if (root.left == null && root.right == null) {
String t = path.reverse().toString();
if (t.compareTo(ans) < 0) {
ans = t;
}
path.reverse();
}
dfs(root.left, path);
dfs(root.right, path);
path.deleteCharAt(path.length() - 1);
}
}
}
// Accepted solution for LeetCode #988: Smallest String Starting From Leaf
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func smallestFromLeaf(root *TreeNode) string {
ans := ""
var dfs func(root *TreeNode, path string)
dfs = func(root *TreeNode, path string) {
if root == nil {
return
}
path = string('a'+root.Val) + path
if root.Left == nil && root.Right == nil {
if ans == "" || path < ans {
ans = path
}
return
}
dfs(root.Left, path)
dfs(root.Right, path)
}
dfs(root, "")
return ans
}
# Accepted solution for LeetCode #988: Smallest String Starting From Leaf
# 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
class Solution:
def smallestFromLeaf(self, root: TreeNode) -> str:
ans = chr(ord('z') + 1)
def dfs(root, path):
nonlocal ans
if root:
path.append(chr(ord('a') + root.val))
if root.left is None and root.right is None:
ans = min(ans, ''.join(reversed(path)))
dfs(root.left, path)
dfs(root.right, path)
path.pop()
dfs(root, [])
return ans
// Accepted solution for LeetCode #988: Smallest String Starting From Leaf
struct Solution;
use rustgym_util::*;
trait Preorder {
fn preorder(&self, cur: &mut Vec<char>, min: &mut String);
}
impl Preorder for TreeLink {
fn preorder(&self, cur: &mut Vec<char>, min: &mut String) {
if let Some(node) = self {
let node = node.borrow();
let val = (node.val as u8 + b'a') as char;
cur.push(val);
if node.left.is_none() && node.right.is_none() {
let s: String = cur.iter().rev().copied().collect();
if min.is_empty() {
*min = s;
} else {
if s < *min {
*min = s;
}
}
}
node.left.preorder(cur, min);
node.right.preorder(cur, min);
cur.pop();
}
}
}
impl Solution {
fn smallest_from_leaf(root: TreeLink) -> String {
let mut cur: Vec<char> = vec![];
let mut res: String = "".to_string();
root.preorder(&mut cur, &mut res);
res
}
}
#[test]
fn test() {
let root = tree!(
0,
tree!(1, tree!(3), tree!(4)),
tree!(2, tree!(3), tree!(4))
);
let res = "dba".to_string();
assert_eq!(Solution::smallest_from_leaf(root), res);
let root = tree!(
25,
tree!(1, tree!(1), tree!(3)),
tree!(3, tree!(0), tree!(2))
);
let res = "adz".to_string();
assert_eq!(Solution::smallest_from_leaf(root), res);
let root = tree!(
2,
tree!(2, None, tree!(1, tree!(0), None)),
tree!(1, tree!(0), None)
);
let res = "abc".to_string();
assert_eq!(Solution::smallest_from_leaf(root), res);
}
// Accepted solution for LeetCode #988: Smallest String Starting From Leaf
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #988: Smallest String Starting From Leaf
// /**
// * Definition for a binary tree node.
// * public class TreeNode {
// * int val;
// * TreeNode left;
// * TreeNode right;
// * TreeNode() {}
// * TreeNode(int val) { this.val = val; }
// * TreeNode(int val, TreeNode left, TreeNode right) {
// * this.val = val;
// * this.left = left;
// * this.right = right;
// * }
// * }
// */
// class Solution {
// private StringBuilder path;
// private String ans;
//
// public String smallestFromLeaf(TreeNode root) {
// path = new StringBuilder();
// ans = String.valueOf((char) ('z' + 1));
// dfs(root, path);
// return ans;
// }
//
// private void dfs(TreeNode root, StringBuilder path) {
// if (root != null) {
// path.append((char) ('a' + root.val));
// if (root.left == null && root.right == null) {
// String t = path.reverse().toString();
// if (t.compareTo(ans) < 0) {
// ans = t;
// }
// path.reverse();
// }
// dfs(root.left, path);
// dfs(root.right, path);
// path.deleteCharAt(path.length() - 1);
// }
// }
// }
Use this to step through a reusable interview workflow for this problem.
Generate every possible combination without any filtering. At each of n positions we choose from up to n options, giving nⁿ total candidates. Each candidate takes O(n) to validate. No pruning means we waste time on clearly invalid partial solutions.
Backtracking explores a decision tree, but prunes branches that violate constraints early. Worst case is still factorial or exponential, but pruning dramatically reduces the constant factor in practice. Space is the recursion depth (usually O(n) for n-level decisions).
Review these before coding to avoid predictable interview regressions.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.