Smallest String Starting From Leaf

LeetCode Q 988 - Smallest String Starting From Leaf

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:

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

Solution: DFS

Code:

public String smallestFromLeaf(TreeNode root) {
  return dfs(root, "");
}

private String dfs(TreeNode root, String suffix) {
  if (root == null) return suffix;

  suffix = (char)('a' + root.val) + suffix;

  if (root.left == null && root.right == null) return suffix;

  if (root.left == null) return dfs(root.right, suffix);

  if (root.right == null) return dfs(root.left, suffix);

  String l = dfs(root.left, suffix);
  String r = dfs(root.right, suffix);

  return l.compareTo(r) <= 0 ? l : r;
}