Smallest String Starting From Leaf - Pre-Order DFS

Problem: https://leetcode.com/problems/smallest-string-starting-from-leaf/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]
Output: "adz"

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 1000.
2. Each node in the tree will have a value between 0 and 25.

The problem can actually be solved with a DFS (Depth-First-Search) and pre-order traversal:

• If you land on a null, return and do nothing
• Landing on a leaf, process the case checking whether this solution is better than the best
• Call Left
• Call Right

Code is below, cheers, ACC.

public class Solution
{
 public string SmallestFromLeaf(TreeNode root)
 {
  string smallest = "";
  SmallestFromLeaf(root, "", ref smallest);
  return smallest;
 }

 private void SmallestFromLeaf(TreeNode node,
         string current,
         ref string smallest)
 {
  if (node == null) return;
  if (node.left == null && node.right == null)
  {
   current = ((char)(node.val + (int)'a')).ToString() + current;
   if (!String.IsNullOrEmpty(current) && (String.IsNullOrEmpty(smallest) || current.CompareTo(smallest) < 0))
   {
    smallest = current;
   }
   return;
  }

  SmallestFromLeaf(node.left, ((char)(node.val + (int)'a')).ToString() + current, ref smallest);
  SmallestFromLeaf(node.right, ((char)(node.val + (int)'a')).ToString() + current, ref smallest);
 }
}