Smallest String Starting From Leaf solution and explanation
Google
9 more videos on this problem
Smallest String Starting From Leaf - Leetcode 988 - PythonNeetCodeIO · 9:23 · 12K views
Smallest String Starting From Leaf | DFS | BFS | Google | Leetcode 988 | codestorywithMIKcodestorywithMIK · 25:37 · 9K views
988. Smallest String Starting From Leaf | Tree | DFS | Recursion & Backtracking | Divide & ConquerAryan Mittal · 24:25 · 3K views
988. Smallest String Starting From Leaf | leetcode daily challenge | DSA | Hindi | shashwatShashCode · 16:57 · 1K views
988. Smallest String Starting From Leaf (Leetcode Medium)Programming Live with Larry · 16:35 · 414 views
LeetCode 988 - Smallest String Starting From Leaf - JavaAlpha-Code · 13:04 · 74 views
Smallest String Starting From Leaf, Medium, LeetCode 988H William Polenz · 11:18 · 69 views
leetcode 988. Smallest String Starting From Leaf - traversalCode-Yao · 12:09 · 67 views
Smallest String Starting From Leaf | Leetcode 988 | Approach + Code with explanation.Pirai's Academy · 11:05 · 65 views
LeetCode 988: Smallest String Starting From Leaf | Java Code Tutorial | Developer CoderDeveloper Coder · 20:20 · 36 views
The problem
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.
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:
- The number of nodes in the tree is in the range
[1, 8500]. 0 <= Node.val <= 25
Approach overview
Problem Overview: Each node in the binary tree stores a value from 0–25 representing characters 'a' to 'z'. A valid string is built by starting at a leaf and moving upward to the root. The task is to return the lexicographically smallest such string among all leaf‑to‑root paths.
Approach 1: Generate All Leaf Strings (DFS + Store Paths) (Time: O(n * h), Space: O(n * h))
Run a Depth-First Search from the root and maintain the current path of characters. When a leaf node is reached, reverse the path to convert the root‑to‑leaf order into the required leaf‑to‑root string. Store each generated string in a list and compare them lexicographically after traversal to find the smallest one. This approach is straightforward because it separates traversal and comparison logic. The drawback is memory usage: storing every leaf string can take O(n * h) space in skewed trees where many paths are long.
Approach 2: DFS with Backtracking and Running Minimum (Time: O(n * h), Space: O(h))
A more efficient solution performs a single DFS while maintaining the current path using a mutable structure such as a list or string builder. Each node contributes a character computed with chr(ord('a') + node.val). When the traversal reaches a leaf, construct the candidate string by reversing the path and compare it directly with the current best result. If the candidate is lexicographically smaller, update the answer. Backtracking removes the last character before returning to the parent node, keeping the path accurate for sibling branches.
This method avoids storing all candidate strings. Only the current traversal path of length h is kept in memory, where h is the tree height. The algorithm still visits every node once in the binary tree, but comparisons happen only when reaching leaves. Because string comparisons may examine up to h characters, the total time complexity becomes O(n * h). The approach naturally fits recursive DFS patterns commonly used for tree problems.
Recommended for interviews: The DFS with backtracking approach is the expected solution. Interviewers want to see that you can traverse a tree while maintaining a path and update results only at leaf nodes. Mentioning the simpler "store all strings" version shows understanding of the problem, but implementing the in‑place DFS solution demonstrates stronger control of recursion, path tracking, and lexicographic comparison.
Approach 1: Depth-First Search (DFS)
In this approach, we utilize depth-first search to explore each path from the leaf to the root. We maintain the current path in a string, which is reversed each time we reach a leaf node. We then compare it to the currently known smallest string, updating the smallest string if the new path is smaller.
class Solution:
def smallestFromLeaf(self, root: TreeNode) -> str:
def dfs(node, path):
if not node:
return
# Prepend character corresponding to the current node's value to the path
path = chr(node.val + ord('a')) + path
# If leaf node
if not node.left and not node.right:
nonlocal smallest
if path < smallest:
smallest = path
# Recurse to children
dfs(node.left, path)
dfs(node.right, path)
smallest = "~" # Start with a string larger than any possible result
dfs(root, "")
return smallestclass Solution {
private String smallest = "~";
public String smallestFromLeaf(TreeNode root) {
dfs(root, "");
return smallest;
}
private void dfs(TreeNode node, String path) {
if (node == null) return;
path = (char)(node.val + 'a') + path;
if (node.left == null && node.right == null) {
if (path.compareTo(smallest) < 0) smallest = path;
}
dfs(node.left, path);
dfs(node.right, path);
}
}#include <string>
using namespace std;
class Solution {
public:
string smallestFromLeaf(TreeNode* root) {
smallest = "~";
dfs(root, "");
return smallest;
}
private:
string smallest;
void dfs(TreeNode* node, string path) {
if (node == nullptr) return;
path = char(node->val + 'a') + path;
if (!node->left && !node->right) {
if (path < smallest) smallest = path;
}
dfs(node->left, path);
dfs(node->right, path);
}
};var smallestFromLeaf = function(root) {
let smallest = "~";
const dfs = (node, path) => {
if (!node) return;
path = String.fromCharCode(node.val + 97) + path;
if (!node.left && !node.right) {
if (path < smallest) smallest = path;
}
dfs(node.left, path);
dfs(node.right, path);
};
dfs(root, "");
return smallest;
};#include <string.h>
#include <limits.h>
void dfs(TreeNode* node, char* path, char* smallest, int pathLen) {
if (!node) return;
path[pathLen++] = node->val + 'a';
path[pathLen] = '\0';
if (!node->left && !node->right) {
if (strcmp(path, smallest) < 0) strcpy(smallest, path);
}
dfs(node->left, path, smallest, pathLen);
dfs(node->right, path, smallest, pathLen);
pathLen--;
}
char* smallestFromLeaf(TreeNode* root) {
char* smallest = (char*)malloc(8500);
memset(smallest, '~', 8500);
char path[8500];
dfs(root, path, smallest, 0);
return strdup(smallest);
}public class Solution {
private string smallest = "~";
public string SmallestFromLeaf(TreeNode root) {
Dfs(root, "");
return smallest;
}
private void Dfs(TreeNode node, string path) {
if (node == null) return;
path = (char)(node.val + 'a') + path;
if (node.left == null && node.right == null) {
if (string.Compare(path, smallest) < 0) smallest = path;
}
Dfs(node.left, path);
Dfs(node.right, path);
}
}This solution uses a DFS approach to explore all paths from leaf nodes to the root. We build the path string by prepending the current node's character (converted from the node's value) to the path. Upon reaching a leaf node, we compare the constructed path to the smallest recorded path. If it's smaller, we update our smallest value. Finally, we use recursion to explore both left and right children of each node.
Time Complexity: O(n) since we may potentially visit every node in the tree. Space Complexity: O(h) where h is the height of the tree due to the recursion stack.
Approach 2: Default Approach
/**
* 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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) | Time Complexity: O(n) since we may potentially visit every node in the tree. Space Complexity: O(h) where h is the height of the tree due to the recursion stack. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS storing all leaf strings | O(n * h) | O(n * h) | Useful for quick implementation or debugging when memory is not a concern |
| DFS with backtracking and running minimum | O(n * h) | O(h) | Preferred interview solution; minimizes memory and processes each path during traversal |
Frequently asked questions
Is Smallest String Starting From Leaf easy or hard?
Smallest String Starting From Leaf is generally considered a Medium difficulty problem. The traversal itself is straightforward DFS, but handling path construction, reversing strings correctly, and performing lexicographic comparisons during recursion adds moderate complexity.
Smallest String Starting From Leaf Python/Java solution
In Python or Java, implement a recursive DFS function that tracks the current path. Convert node values to characters using 'a' + value, append to the path, and when a leaf is reached compare the reversed string with the current best result. After exploring children, remove the last character to backtrack.
How to solve Smallest String Starting From Leaf in O(n)?
Traversal of the tree itself is O(n) using Depth-First Search, since every node is visited once. The overall complexity becomes O(n * h) because candidate strings may require comparisons up to the height of the tree. Implement DFS with backtracking, maintain the path characters, and update the smallest lexicographic string whenever a leaf is reached.
What is the best approach for Smallest String Starting From Leaf?
Depth-First Search (DFS) with backtracking is the best approach. Traverse the tree while maintaining the current path of characters. When a leaf node is reached, reverse the path to form the leaf‑to‑root string and compare it with the smallest string found so far. This method processes the tree in one pass and keeps only the current path in memory.
Is Smallest String Starting From Leaf asked at Google/Amazon/Meta?
Tree traversal and DFS path problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. Variations that involve building strings from tree paths or comparing lexicographic results are common because they test recursion, backtracking, and binary tree traversal skills.
What data structure is used in Smallest String Starting From Leaf?
The main data structure is a binary tree combined with a DFS traversal stack (implicit through recursion). A list or string builder is used to maintain the current path of characters during traversal. Backtracking removes characters as recursion returns to parent nodes.
What is the time complexity of Smallest String Starting From Leaf?
The time complexity is O(n * h), where n is the number of nodes and h is the height of the tree. Each node is visited once during DFS, and when a leaf is encountered the algorithm may compare strings up to length h. Space complexity is O(h) due to the recursion stack and current path storage.