Leetcode 988. Smallest String Starting From Leaf
Problem Description
In this problem, we have a binary tree where each node represents a letter from 'a' to 'z'. 'a' is represented by 0, 'b' is represented by 1, and so on up to 'z' represented by 25.
The task is to find the lexicographically smallest string that starts at a leaf of this tree and ends at the root of this binary tree. Here, "lexicographically smaller" means that in the two strings x and y, if x is a prefix of y then x is lexicographically smaller than y. Or if x[i] < y[i] and for all j < i, x[j] = y[j], then x is lexicographically smaller than y.
Example
For example, let's say your binary tree looked like this:
1 2 3 3 4 / \ 5 0 1
Here, the lexicographically smallest string that starts from a leaf and ends at the root would be "da". This string is formed by traversing from the left child node (a) of the root to the root itself (d).
Approach/Solution
We use a recursive depth-first search (DFS) in this problem solution. This allows us to visit all the nodes in the binary tree, and specifically allows us to start at the leaf nodes and work our way back towards the root, collecting the character values at each node along the way.
The algorithm works like this:
-
We declare a string
ans
, which will be the final answer, and initially is an empty string. -
Then, we start DFS recursion, with the current string
path
that is built from the root to the current node, and the smallest stringans
that has been updated so far. -
For each visited node, we add the current letter to
path
, then we move the string to the left and right child, respectively. If the node is a leaf node (i.e., it does not have left or right child), we reverse thepath
, compare and update the smallest stringans
. At the end, we reversepath
to its original order and backtrack to the parent node bypop_back()
. -
After visiting all nodes, we return the smallest string
ans
.
Python Solution
1 2python 3class Solution: 4 def smallestFromLeaf(self, root): 5 ans = "" 6 def dfs(node, path): 7 if node: 8 path = chr(node.val + ord('a')) + path 9 if not node.left and not node.right: 10 nonlocal ans 11 ans = min(ans, path) if ans else path 12 dfs(node.left, path) 13 dfs(node.right, path) 14 dfs(root, "") 15 return ans
Java Solution
1 2java 3class Solution { 4 String ans = "~"; 5 public String smallestFromLeaf(TreeNode root) { 6 dfs(root, new StringBuilder()); 7 return ans; 8 } 9 10 public void dfs(TreeNode node, StringBuilder sb) { 11 if (node == null) return; 12 sb.append((char)('a' + node.val)); 13 14 if (node.left == null && node.right == null) { 15 sb.reverse(); 16 String S = sb.toString(); 17 sb.reverse(); 18 19 if (S.compareTo(ans) < 0) ans = S; 20 } 21 22 dfs(node.left, sb); 23 dfs(node.right, sb); 24 sb.deleteCharAt(sb.length() - 1); 25 } 26}
JavaScript Solution
1
2javascript
3var smallestFromLeaf = function(root) {
4 const letterList = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"];
5 return dfs(root, "");
6
7 function dfs(node, string) {
8 if (!node) return string;
9 string = letterList[node.val] + string;
10 if (!node.left && !node.right) return string;
11 if (!node.right) return dfs(node.left, string);
12 if (!node.left) return dfs(node.right, string);
13 let left = dfs(node.left, string);
14 let right = dfs(node.right, string);
15 return left < right ? left : right;
16 }
17};
C++ Solution
1
2c++
3class Solution {
4public:
5 string smallestFromLeaf(TreeNode* root) {
6 string ans;
7 dfs(root, "", ans);
8 return ans;
9 }
10
11 private:
12 void dfs(TreeNode* root, string&& path, string& ans) {
13 if (root == nullptr)
14 return;
15
16 path.push_back(root->val + 'a');
17
18 if (root->left == nullptr && root->right == nullptr) {
19 reverse(begin(path), end(path));
20 if (ans.empty() || ans > path)
21 ans = path;
22 reverse(begin(path), end(path));
23 }
24
25 dfs(root->left, move(path), ans);
26 dfs(root->right, move(path), ans);
27 path.pop_back();
28 }
29};
C# Solution
1
2csharp
3public class Solution {
4 public string SmallestFromLeaf(TreeNode root) {
5 var ans = new List<int>();
6 Dfs(root, new List<int>(), ref ans);
7 return new string(ans.Select(x => (char)('a' + x)).ToArray());
8 }
9
10 private void Dfs(TreeNode node, List<int> path, ref List<int> ans) {
11 if(node == null) return;
12
13 path.Add(node.val);
14
15 if(node.left == null && node.right == null) {
16 path.Reverse();
17 if(ans.Count == 0 || LexicographicallySmaller(path, ans)) ans = new List<int>(path);
18 path.Reverse();
19 }
20
21 Dfs(node.left, path, ref ans);
22 Dfs(node.right, path, ref ans);
23
24 path.RemoveAt(path.Count - 1);
25 }
26
27 private bool LexicographicallySmaller(List<int> a, List<int> b) {
28 for(int i=0; i < a.Count && i < b.Count; i++) {
29 if(a[i] != b[i]) return a[i] < b[i];
30 }
31 return a.Count < b.Count;
32 }
33}
Each solution uses a DFS recursion to check all possible paths from root to leaf nodes. For each sub tree, the function checks if it's a leaf node and if so, it constructs the path string (a possible candidate for the final answer). Then, it updates the result ans
if the current path string is lexicographically smaller. Otherwise, the function will backtrace to the upper level.The main function calls the DFS function to begin the traversal of the binary tree. We represent each letter in the binary tree as an integer, and we convert from integer to character using the built-in functions ord
and chr
in Python, (char)
and +
operator in Java, letterList
in JavaScript, (char)('a' + x)
in C#, and 'a' + int
in C++.
In Java, StringBuilder
class is used to store the path string. StringBuilder
's append
method concatenates a single character, and its reverse
method is used to reverse the order of characters in StringBuilder
object. When it finds a leaf node, it checks whether the newly created string is lesser than ans
. If true, it updates ans
and then reverses the string back to its original form. The deleteCharAt
method is used to delete the last character of StringBuilder
object when backtracking, which resembles pop_back
in Python.
In JavaScript, we form a list of English lowercase alphabets and use it to transform the value of each node to its representative letter. The array's index is equivalent to the node value, and the node value to character conversion is done by indexing enough alphabets by the node value. left < right
is an easy way to analyze two strings in JavaScript.
In C++, we use push_back
to append a character to the back of the string path
, and pop_back
to remove the last character from the string path
. The reverse of the string is done using reverse(begin(path), end(path))
.
In C#, Select
is a powerful built-in method that applies a specified function to the elements of an IList and returns the resulting list. We use this method to convert the list of integer node values to a list of characters represented by them. The RemoveAt
method is used to remove an element at a specific position from List object.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.