988. Smallest String Starting From Leaf LeetCode Solution

In this guide, you will get 988. Smallest String Starting From Leaf LeetCode Solution with the best time and space complexity. The solution to Smallest String Starting From Leaf problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Smallest String Starting From Leaf solution in C++
Smallest String Starting From Leaf solution in Java
Smallest String Starting From Leaf solution in Python
Additional Resources

988. Smallest String Starting From Leaf LeetCode Solution image

Problem Statement of Smallest String Starting From Leaf

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]
Output: “adz”

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

Complexity Analysis

Time Complexity: O(nh), where h = |\texttt{path}| = \text{height(tree)} for comparison
Space Complexity: O(h)

988. Smallest String Starting From Leaf LeetCode Solution in C++

class Solution {
 public:
  string smallestFromLeaf(TreeNode* root) {
    string ans;
    dfs(root, "", ans);
    return ans;
  }

 private:
  void dfs(TreeNode* root, string&& path, string& ans) {
    if (root == nullptr)
      return;

    path.push_back(root->val + 'a');

    if (root->left == nullptr && root->right == nullptr) {
      ranges::reverse(path);
      if (ans == "" || ans > path)
        ans = path;
      ranges::reverse(path);  // Roll back.
    }

    dfs(root->left, std::move(path), ans);
    dfs(root->right, std::move(path), ans);
    path.pop_back();
  }
};
/* code provided by PROGIEZ */

988. Smallest String Starting From Leaf LeetCode Solution in Java

class Solution {
  public String smallestFromLeaf(TreeNode root) {
    dfs(root, new StringBuilder());
    return ans;
  }

  private String ans = null;

  private void dfs(TreeNode root, StringBuilder sb) {
    if (root == null)
      return;

    sb.append((char) (root.val + 'a'));

    if (root.left == null && root.right == null) {
      final String path = sb.reverse().toString();
      sb.reverse(); // Roll back.
      if (ans == null || ans.compareTo(path) > 0)
        ans = path;
    }

    dfs(root.left, sb);
    dfs(root.right, sb);
    sb.deleteCharAt(sb.length() - 1);
  }
}
// code provided by PROGIEZ