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:

1. We declare a string ans, which will be the final answer, and initially is an empty string.

2. Then, we start DFS recursion, with the current string path that is built from the root to the current node, and the smallest string ans that has been updated so far.

3. 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 the path, compare and update the smallest string ans. At the end, we reverse path to its original order and backtrack to the parent node by pop_back().

4. 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.