Smallest String Starting From Leaf

class Solution {
public:
    string findSmallestLeafPath(TreeNode* root) {
        string smallest = "";
        queue<pair<TreeNode*, string>> workQueue;
    
        workQueue.push({root, string(1, root->val + 'a')});
    
        while (!workQueue.empty()) {
            auto[currNode, path] = workQueue.front();
            workQueue.pop();
    
            if (!currNode->left && !currNode->right) {
                if (smallest == "") {
                    smallest = path;
                } else {
                    smallest = min(smallest, path);
                }
            }
    
            if (currNode->left) {
                workQueue.push({currNode->left, char(currNode->left->val + 'a') + path});
            }
    
            if (currNode->right) {
                workQueue.push({currNode->right, char(currNode->right->val + 'a') + path});
            }
        }
    
        return smallest;
    }
};

To solve the problem of finding the smallest string starting from any leaf in a binary tree, where each node represents a letter, the given C++ code illustrates an efficient approach:

• Start by defining a function within a class named Solution that will process a given binary tree and return the smallest lexicographical string from the leaves back to the root.
• Use a queue to perform a breadth-first search (BFS). This queue stores a pair consisting of the current tree node and the string formed by the path to that node.
• Initialize the queue with the root node. Convert the value of the node to the corresponding character and form the initial string.
• Enter a loop that continues until the queue is empty. Inside the loop:
  • Dequeue the front pair, which includes the current node and the path string.
  • Check if the current node is a leaf (no left or right child):
    • For leaf nodes, compare the path string with the previously found smallest string. Update the smallest string if the new one is lexicographically smaller.
  • For non-leaf nodes:
    • If there is a left child, enqueue the left child and append its character to the current path string.
    • Similarly, enqueue the right child if it exists, again updating the path string.
• After the loop finishes, the variable smallest holds the smallest string formed from leaf to root. Return this string.

This approach ensures you systematically explore all paths from the root to the leaves, updating the smallest string as paths are checked. Through BFS, every node's value contributes to forming potential paths, efficiently comparing and finding the lexicographically smallest string possible from leaf to root.

class Solution {
    public String minimumLeafPath(TreeNode root) {
        String minPath = "";
        Queue<Pair<TreeNode, String>> traversalQueue = new LinkedList<>();
    
        traversalQueue.add(new Pair<>(root, String.valueOf((char)(root.val + 'a'))));
    
        while (!traversalQueue.isEmpty()) {
            Pair<TreeNode, String> treeNodePair = traversalQueue.poll();
            TreeNode currentNode = treeNodePair.getKey();
            String pathSoFar = treeNodePair.getValue();
        
            if (currentNode.left == null && currentNode.right == null) {
                if (minPath.isEmpty()) {
                    minPath = pathSoFar;
                } else {
                    minPath = pathSoFar.compareTo(minPath) < 0 ? pathSoFar : minPath;
                }
            }
    
            if (currentNode.left != null) {
                traversalQueue.add(new Pair<>(currentNode.left, (char)(currentNode.left.val + 'a') + pathSoFar));
            }
    
            if (currentNode.right != null) {
                traversalQueue.add(new Pair<>(currentNode.right, (char)(currentNode.right.val + 'a') + pathSoFar));
            }
        }
    
        return minPath;
    }
}

In the provided Java solution, the goal is to find the smallest lexicographical string from the leaf to the root in a binary tree. Each node in the tree contains an integer value that corresponds to a lowercase letter ('a' to 'z', given by 0 to 25). The solution employs a breadth-first search (BFS) using a queue to explore all paths from root to the tree's leaves.

• Initialize an empty string minPath to store the smallest path discovered.
• Use a Queue to facilitate BFS, where each element is a Pair consisting of a TreeNode and the current path string formed from the root to this node.
• The root of the tree is added to the queue initially, with its path string being just its corresponding character.
• A loop runs as long as there are nodes to process in the queue:
  • Dequeue the next node and path.
  • If the dequeued node is a leaf (i.e., it has no children):
    • If minPath is still empty or the new path is lexicographically smaller, update minPath.
  • For each existing child of the current node, construct the new path by adding the child's character to the current path and enqueue the child and this new path.
• Continue this process until all paths leading to leaves are evaluated.
• Return the smallest path minPath found, which will be the lexicographically smallest string from any leaf to the root.

This approach efficiently determines the desired path by continuously updating the smallest path found during the BFS traversal.

class Solution:
    def findSmallestString(self, root: Optional[TreeNode]) -> str:
        least_val = ""
        queue = deque()
            
        queue.append([root, chr(root.val + ord('a'))])
            
        while queue:
            node, str_val = queue.popleft()
                
            if not node.left and not node.right:
                least_val = min(least_val, str_val) if least_val else str_val
                
            if node.left:
                queue.append([node.left, chr(node.left.val + ord('a')) + str_val])
                
            if node.right:
                queue.append([node.right, chr(node.right.val + ord('a')) + str_val])
    
        return least_val

The provided Python code defines a method findSmallestString within the Solution class aimed at finding the lexicographically smallest string from a given binary tree, where each node's value represents a character (using the English lowercase letters). The method utilizes a breadth-first search strategy, transforming each node's integer value into its corresponding character and building strings as it traverses from the root to the leaves.

Understand the key steps of the code:

1. Initialize an empty string least_val to store the smallest string.
2. Use a deque named queue to hold nodes along with their corresponding string values as the tree is traversed.
3. Begin by appending the root node and its character representation to the queue.
4. Process each node in the queue:
   • Extract the node and its string value.
   • If the current node is a leaf (no left or right children):
     • Compare the current string with least_val to keep track of the smallest string.
   • If the node has a left child, append it to the queue, prepending the left child’s character to the current string value.
   • If the node has a right child, similarly append it to the queue but prepend the right child's character.
5. Finally, return the smallest string found, least_val.

This approach ensures that by the end of the traversal, the smallest lexicographical string formed from the root to any leaf in the binary tree is identified and returned.