##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/988.html

# 988. Smallest String Starting From Leaf

Medium

## Description

Given the root of a binary tree, each node has a value from 0 to 25 representing the letters 'a' to 'z': a value of 0 represents 'a', a value of 1 represents 'b', and so on.

Find 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: [0,1,2,3,4,3,4]

Output: “dba”

Example 2:

Input: [25,1,3,1,3,0,2]

Example 3:

Input: [2,2,1,null,1,0,null,0]

Output: “abc”

Note:

1. The number of nodes in the given tree will be between 1 and 8500.
2. Each node in the tree will have a value between 0 and 25.

## Solution

Do breadth first search. Initially, for each node, the string is reversed, which means the string starts from root and ends at the current node. If a leaf is met, reverse the string and update the smallest string starting from leaf. Finally, return the smallest string.

• /**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
String smallestStr = "";

public String smallestFromLeaf(TreeNode root) {
if (root == null)
return smallestStr;
nodeQueue.offer(root);
strQueue.offer(new StringBuffer(String.valueOf((char) ('a' + root.val))));
while (!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.poll();
StringBuffer sb = strQueue.poll();
TreeNode left = node.left, right = node.right;
if (left == null && right == null) {
sb.reverse();
String str = sb.toString();
if (smallestStr.length() == 0 || str.compareTo(smallestStr) < 0)
smallestStr = str;
sb.reverse();
} else {
if (left != null) {
StringBuffer leftSB = new StringBuffer(sb.toString());
leftSB.append((char) ('a' + left.val));
nodeQueue.offer(left);
strQueue.offer(leftSB);
}
if (right != null) {
StringBuffer rightSB = new StringBuffer(sb.toString());
rightSB.append((char) ('a' + right.val));
nodeQueue.offer(right);
strQueue.offer(rightSB);
}
}
}
return smallestStr;
}
}

• // OJ: https://leetcode.com/problems/smallest-string-starting-from-leaf/
// Time: O(N + (logN)^2)
// Space: O(logN)
class Solution {
string ans, path;
void dfs(TreeNode *root) {
if (!root) return;
path += 'a' + root->val;
if (!root->left && !root->right) {
reverse(begin(path), end(path));
if (ans.empty() || path < ans) ans = path;
reverse(begin(path), end(path));
} else {
dfs(root->left);
dfs(root->right);
}
path.pop_back();
}
public:
string smallestFromLeaf(TreeNode* root) {
dfs(root);
return ans;
}
};

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

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def smallestFromLeaf(self, root):
"""
:type root: TreeNode
:rtype: str
"""
res = []
self.dfs(root, "", res)
res.sort()
return res[0]

def dfs(self, root, path, res):
if not root.left and not root.right:
res.append(chr(root.val + ord('a')) + path)
return
if root.left:
self.dfs(root.left, chr(root.val + ord('a')) + path, res)
if root.right:
self.dfs(root.right, chr(root.val + ord('a')) + path, res)

• /**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func smallestFromLeaf(root *TreeNode) string {
ans := ""
var dfs func(root *TreeNode, path string)
dfs = func(root *TreeNode, path string) {
if root == nil {
return
}
path = string('a'+root.Val) + path
if root.Left == nil && root.Right == nil {
if ans == "" || path < ans {
ans = path
}
return
}
dfs(root.Left, path)
dfs(root.Right, path)
}

dfs(root, "")
return ans
}