# 988. Smallest String Starting From Leaf

```
T: O(n)
S: O(n)
```

```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 {
    String[] res;
    public String smallestFromLeaf(TreeNode root) {
        res = new String[1];
        dfs(root, new StringBuilder(), res);
        return res[0];
    }
    private void dfs(TreeNode node, StringBuilder sb, String[] res) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            sb.append((char)(node.val + 'a'));
            String s = sb.reverse().toString();
            //System.out.println(s);
            if (res[0] == null || res[0].compareTo(s) > 0) {
                res[0] = s;
            }
            sb.reverse();
            sb.deleteCharAt(sb.length()-1);
        }

        sb.append((char)(node.val + 'a'));
        dfs(node.left, sb, res);
        dfs(node.right, sb, res);
        sb.deleteCharAt(sb.length()-1);
    }
}

/**
using same memory -> StringBuilder 
has to do backtracking,
if use String, no need backtracking, because everytime it's a new String (but waste memory) 
and create new string makes it become O(n^2) solution

so using StringBuilder is better T: O(n)

T: O(n)
S: O(n)
 */
```

## new version

using global variable

```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 String result;
    public String smallestFromLeaf(TreeNode root) {
        StringBuilder sb = new StringBuilder();

        dfs(root, sb);
        return result;
    }
    // using preorder
    private void dfs(TreeNode node, StringBuilder sb) {
        if (node == null) {
            return;
        }

        sb.append((char)(node.val + 'a')); // backtracking

        // reach leaf, to compare the string
        // because it's a preorder dfs, so needs to reverse String to compare, after that reverse back
        if (node.left == null && node.right == null) {
            String s = sb.reverse().toString();

            if (result == null || s.compareTo(result.toString()) < 0) {
                result = s;
            }
            sb.reverse();
        }

        dfs(node.left, sb);
        dfs(node.right, sb);
        sb.deleteCharAt(sb.length()-1); // backtracking (because we use StringBuilder, same memory)
    }
}
```

no using global, but really hard to know to use sb.setLength(0)

```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 {
    public String smallestFromLeaf(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        StringBuilder result = new StringBuilder();

        dfs(root, sb, result);
        return result.toString();
    }
    // using preorder
    private void dfs(TreeNode node, StringBuilder sb, StringBuilder result) {
        if (node == null) {
            return;
        }

        sb.append((char)(node.val + 'a')); // backtracking

        // reach leaf, to compare the string
        // because it's a preorder dfs, so needs to reverse String, then backtracing it to try
        if (node.left == null && node.right == null) {
            String s = sb.reverse().toString();

            if (result.length() == 0 || s.compareTo(result.toString()) < 0) {
                result.setLength(0);
                result.append(s);
            }
            sb.reverse();
        }

        dfs(node.left, sb, result);
        dfs(node.right, sb, result);
        
        sb.deleteCharAt(sb.length()-1); // backtracking (because we use StringBuilder, same memory)
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/988.-smallest-string-starting-from-leaf.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.