# Smallest String Starting From Leaf Problem

## Description

LeetCode Problem 988.

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:

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

Example 2:

``````1
2
Input: root = [25,1,3,1,3,0,2]
``````

Example 3:

``````1
2
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

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* 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 {
string ans;
public:
void helper(TreeNode *root,string &s) {
if (!root) return;
s.push_back(root->val + 'a');
if (root->left == root->right) {
string str = s;
reverse(str.begin(), str.end());
if (ans.empty() || str < ans)
ans = str;
}
helper(root->left, s);
helper(root->right, s);
s.pop_back();
}

string smallestFromLeaf(TreeNode* root) {
string s = "";
helper(root, s);
return ans;
}
};
``````