# 988. Smallest String Starting From Leaf
Difficulty: Medium

## Solution

/**
*** Author: R-CO
*** E-mail: [e-mail]
*** Date: 2020-11-10
**/
#include <algorithm>
using std::reverse;
#include <cstdlib>
#include <iostream>
using std::cout;
using std::endl;
#include <string>
using std::string;

struct TestCasesStruct {};

/**
 * 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) {}
 * };
 */
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 {
 public:
  string smallestFromLeaf(TreeNode *root) {
    string output(kMaxNodeCount, 'z');

    preorderTraversal(root, "", output);

    return output;
  }

 private:
  void preorderTraversal(TreeNode *node, string current_str, string &output) {
    if (node == nullptr) {
      return;
    }

    current_str += node->val + 'a';
    if (node->left == nullptr && node->right == nullptr) {
      auto reverse_str = current_str;
      reverse(reverse_str.begin(), reverse_str.end());
      if (reverse_str < output) {
        output = move(reverse_str);  // maybe move()
      }

      return;
    }

    preorderTraversal(node->left, current_str, output);
    preorderTraversal(node->right, current_str, output);
  }

  const int kMaxNodeCount = 8500;
};

int main(int argc, char *argv[]) {
  TreeNode root{3};
  root.left = new TreeNode(9);
  root.right = new TreeNode(20, new TreeNode(15), new TreeNode(7));

  Solution solution;
  auto output = solution.smallestFromLeaf(&root);

  return EXIT_SUCCESS;
}

## Result
Success
Details
Runtime: 12 ms, faster than 86.69% of C++ online submissions for Smallest String Starting From Leaf.
Memory Usage: 20.8 MB, less than 5.40% of C++ online submissions for Smallest String Starting From Leaf.

###### tags: `LeetCode-Medium` `C++`