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 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.
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.
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 | 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 | — |
| 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 |
Smallest String Starting From Leaf - Leetcode 988 - Python • NeetCodeIO • 11,864 views views
Watch 9 more video solutions →Practice Smallest String Starting From Leaf with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor