Smallest String Starting From Leaf
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
A straightforward solution using Depth-First Search. We traverse from the root to each leaf. As we descend the tree, we build the leaf-to-root string by prepending the current node's character to the string passed down from the parent. This way, when we reach a leaf, we have the complete leaf-to-root string ready for comparison against the best-so-far.
Algorithm
-
- Initialize a global string
smallestStringto a lexicographically large value (e.g., a string starting with~).
- Initialize a global string
-
- Define a recursive DFS function
dfs(node, currentString).
- Define a recursive DFS function
-
- The initial call is
dfs(root, "").
- The initial call is
-
- In
dfs, create anewStringby prepending the current node's character tocurrentString. This builds the string in the desired leaf-to-root order as the recursion goes deeper.
- In
-
- If the current node is a leaf, compare
newStringwithsmallestString. IfnewStringis smaller, updatesmallestString.
- If the current node is a leaf, compare
-
- If the node is not a leaf, recursively call
dfsfor its non-null children, passing thenewString.
- If the node is not a leaf, recursively call
Walkthrough
This approach uses a recursive helper function that traverses the tree. It keeps track of the path from the current node up to the root.
The path is built by prepending the current node's character to the path string received from the parent.
A dfs(node, currentString) is called, where currentString represents the path from a child of node up to the root.
Inside the function, we form newString = (char)('a' + node.val) + currentString.
When a leaf is reached, newString is a complete leaf-to-root string. We compare it with a global smallestString variable and update it if newString is smaller.
This is conceptually simple but inefficient in Java due to repeated string concatenations, which have a time cost proportional to the string length.
class Solution { String smallestString = "~"; // Use a value larger than any possible string public String smallestFromLeaf(TreeNode root) { if (root == null) return ""; dfs(root, ""); return smallestString; } private void dfs(TreeNode node, String currentString) { // Prepend current node's character String newString = (char)('a' + node.val) + currentString; if (node.left == null && node.right == null) { if (newString.compareTo(smallestString) < 0) { smallestString = newString; } return; } if (node.left != null) { dfs(node.left, newString); } if (node.right != null) { dfs(node.right, newString); } }}Complexity
Time
`O(N*H)`, where `N` is the number of nodes and `H` is the height of the tree. At each node at depth `d`, we create a new string of length `d+1`, which takes `O(d)` time. The sum of depths of all nodes can be up to `O(N*H)` in the worst case (a skewed tree).
Space
`O(H^2)`, where `H` is the height of the tree. The recursion stack goes up to depth H. At each level of the stack, a new string of increasing length is stored (`1 + 2 + ... + H`), leading to a total space of `O(H^2)`. For a skewed tree, this can be `O(N^2)`.
Trade-offs
Pros
The code is very concise and directly models the problem's string definition (leaf-to-root).
It avoids storing all possible path strings, unlike a pure brute-force approach.
Cons
The use of immutable string concatenation (
+) in a recursive function is highly inefficient. Each concatenation creates a new string object, leading to poor time performance.The space complexity is high because each recursive call stores a new string on the call stack. For a tree of height H, this leads to a space usage of O(H^2).
Solutions
Solution
/** * 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 ); } } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.