Smallest String Starting From Leaf

Med

#0942Time: `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)`.

Patterns

Backtracking

Algorithms

Depth-First Search

Data structures

String Tree Binary Tree

Prompt

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

1. Initialize a global string smallestString to a lexicographically large value (e.g., a string starting with ~).
1. Define a recursive DFS function dfs(node, currentString).
1. The initial call is dfs(root, "").
1. In dfs, create a newString by prepending the current node's character to currentString. This builds the string in the desired leaf-to-root order as the recursion goes deeper.
1. If the current node is a leaf, compare newString with smallestString. If newString is smaller, update smallestString.
1. If the node is not a leaf, recursively call dfs for its non-null children, passing the newString.

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.

1class Solution {2    String smallestString = "~"; // Use a value larger than any possible string3 4    public String smallestFromLeaf(TreeNode root) {5        if (root == null) return "";6        dfs(root, "");7        return smallestString;8    }9 10    private void dfs(TreeNode node, String currentString) {11        // Prepend current node's character12        String newString = (char)('a' + node.val) + currentString;13 14        if (node.left == null && node.right == null) {15            if (newString.compareTo(smallestString) < 0) {16                smallestString = newString;17            }18            return;19        }20 21        if (node.left != null) {22            dfs(node.left, newString);23        }24        if (node.right != null) {25            dfs(node.right, newString);26        }27    }28}

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).

This is the most efficient approach. It uses a single StringBuilder to keep track of the current path from the root downwards. When a leaf is reached, the path is reversed temporarily to form the leaf-to-root string and compared with the best-so-far. This avoids the overhead of creating numerous string objects and storing all paths.

Algorithm

1. Initialize a global string smallestString to a lexicographically large value.
1. Define a recursive function dfs(node, sb) that takes the current node and a StringBuilder.
1. In dfs, append the current node's character to sb. This builds a root-to-leaf path.
1. If a leaf node is reached:
- a. Reverse sb to get the temporary leaf-to-root string.
- b. Compare this string with smallestString and update if it's smaller.
- c. Crucially, reverse sb back to its original root-to-leaf state to ensure correctness for subsequent traversals.
1. Recursively call dfs for the left and right children.
1. After the recursive calls for a node's children return, backtrack by removing the current node's character from the end of sb.

Walkthrough

We perform a pre-order DFS traversal using a helper function dfs(node, sb), where sb is a StringBuilder holding the path from the root to the current node. A global variable smallestString tracks the lexicographically smallest string found. In the dfs function, we append the current node's character to sb. If a leaf node is reached, we have a root-to-leaf path. We create the leaf-to-root string by reversing sb, compare it with smallestString, and update if it's smaller. After the comparison, we must reverse sb back to its original state (root-to-leaf order) so that the StringBuilder is correct for the rest of the traversal. For backtracking, after visiting a node and its children, we remove the node's character from the end of sb. This method is efficient because StringBuilder appends and deletes at the end in O(1) time. The only expensive operation (reversal, O(H)) is performed only at the leaf nodes.

1class Solution {2    String smallestString = "~"; // Use a value larger than any possible string3 4    public String smallestFromLeaf(TreeNode root) {5        if (root == null) return "";6        dfs(root, new StringBuilder());7        return smallestString;8    }9 10    private void dfs(TreeNode node, StringBuilder sb) {11        sb.append((char)('a' + node.val));12 13        if (node.left == null && node.right == null) {14            String currentString = sb.reverse().toString();15            if (currentString.compareTo(smallestString) < 0) {16                smallestString = currentString;17            }18            // Reverse back to restore the StringBuilder for backtracking19            sb.reverse();20        }21 22        if (node.left != null) {23            dfs(node.left, sb);24        }25        if (node.right != null) {26            dfs(node.right, sb);27        }28 29        // Backtrack by removing the current node's character30        sb.setLength(sb.length() - 1);31    }32}

Complexity

Time

`O(N + L*H)`, where `N` is the number of nodes, `L` is the number of leaves, and `H` is the tree height. The traversal visits each of the N nodes once (`O(N)`). At each of the `L` leaf nodes, we perform work proportional to the height `H` (for reversing and comparing). In the worst case of a skewed tree, this is `O(N)`, and for a complete tree, it's `O(N log N)`.

Space

`O(H)`, where `H` is the height of the tree. The space is dominated by the recursion stack depth and the `StringBuilder`, both of which are at most the height of the tree.

Trade-offs

Pros

Optimal time complexity for this problem by minimizing expensive operations.
Optimal space complexity, using only O(H) extra space for the recursion stack and the StringBuilder.

Cons

The logic of reversing the StringBuilder and then reversing it back can be slightly more complex to reason about compared to a more direct approach.

Solutions

Solution

1/** * 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 ); } } }

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: string ans = "" ; string smallestFromLeaf ( TreeNode * root ) { string path = "" ; dfs ( root , path ); return ans ; } void dfs ( TreeNode * root , string & path ) { if ( ! root ) return ; path += 'a' + root -> val ; if ( ! root -> left && ! root -> right ) { string t = path ; reverse ( t . begin (), t . end ()); if ( ans == "" || t < ans ) ans = t ; } dfs ( root -> left , path ); dfs ( root -> right , path ); path . pop_back (); } };

1# 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

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.

← Previous

Previous problem

Next problem