# Smallest String Starting From Leaf
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/smallest-string-starting-from-leaf)
Canonical: https://scaleengineer.com/dsa/problems/smallest-string-starting-from-leaf
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** String, Tree, Binary Tree
---
## 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:**

![](https://assets.glich.co/dsa/smallest-string-starting-from-leaf/image0.png) 

**Input:** root = [0,1,2,3,4,3,4]
**Output:** "dba"

**Example 2:**

![](https://assets.glich.co/dsa/smallest-string-starting-from-leaf/image1.png) 

**Input:** root = [25,1,3,1,3,0,2]
**Output:** "adz"

**Example 3:**

![](https://assets.glich.co/dsa/smallest-string-starting-from-leaf/image2.png) 

**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
## Simple Recursive DFS
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.
**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)`.
**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).
### Explanation
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.

```java
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);
        }
    }
}
```
### Algorithm
- 1. Initialize a global string `smallestString` to a lexicographically large value (e.g., a string starting with `~`).
- 2. Define a recursive DFS function `dfs(node, currentString)`.
- 3. The initial call is `dfs(root, "")`.
- 4. 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.
- 5. If the current node is a leaf, compare `newString` with `smallestString`. If `newString` is smaller, update `smallestString`.
- 6. If the node is not a leaf, recursively call `dfs` for its non-null children, passing the `newString`.

## Efficient DFS with StringBuilder
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    String smallestString = "~"; // Use a value larger than any possible string

    public String smallestFromLeaf(TreeNode root) {
        if (root == null) return "";
        dfs(root, new StringBuilder());
        return smallestString;
    }

    private void dfs(TreeNode node, StringBuilder sb) {
        sb.append((char)('a' + node.val));

        if (node.left == null && node.right == null) {
            String currentString = sb.reverse().toString();
            if (currentString.compareTo(smallestString) < 0) {
                smallestString = currentString;
            }
            // Reverse back to restore the StringBuilder for backtracking
            sb.reverse();
        }

        if (node.left != null) {
            dfs(node.left, sb);
        }
        if (node.right != null) {
            dfs(node.right, sb);
        }

        // Backtrack by removing the current node's character
        sb.setLength(sb.length() - 1);
    }
}
```
### Algorithm
- 1. Initialize a global string `smallestString` to a lexicographically large value.
- 2. Define a recursive function `dfs(node, sb)` that takes the current node and a `StringBuilder`.
- 3. In `dfs`, append the current node's character to `sb`. This builds a root-to-leaf path.
- 4. 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.
- 5. Recursively call `dfs` for the left and right children.
- 6. After the recursive calls for a node's children return, backtrack by removing the current node's character from the end of `sb`.

# Solutions
### Java

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

### CPP

```cpp
/** * 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 (); } };
```

### Python

```python
# 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
```