## DEV Community

MD ARIFUL HAQUE

Posted on • Updated on

# 988. Smallest String Starting From Leaf

Medium

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:

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

Example 2:

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

Example 3:

• 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`
``````    /**
* Definition for a binary tree node.
* class TreeNode {
*     public \$val = null;
*     public \$left = null;
*     public \$right = null;
*     function __construct(\$val = 0, \$left = null, \$right = null) {
*         \$this->val = \$val;
*         \$this->left = \$left;
*         \$this->right = \$right;
*     }
* }
*/
class Solution {

/**
* @param TreeNode \$root
* @return String
*/
function smallestFromLeaf(\$root) {
\$ans = "";
\$this->dfs(\$root, "", \$ans);
return \$ans;
}

private function dfs(\$root, \$path, &\$ans) {
if (\$root == null)
return;

\$path .= chr(\$root->val + ord('a'));

if (\$root->left == null && \$root->right == null) {
\$path = strrev(\$path);
if (\$ans == "" || \$ans > \$path)
\$ans = \$path;
\$path = strrev(\$path);  // Roll back.
}

\$this->dfs(\$root->left, \$path, \$ans);
\$this->dfs(\$root->right, \$path, \$ans);
\$path = substr(\$path, 0, -1);
}
}

``````