988. Smallest String Starting From Leaf - Leetcode Solution

Code Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
        self.result = "~"  # '~' is lexicographically larger than any lowercase string

        def dfs(node, path):
            if not node:
                return
            # Prepend current character to path (since we want leaf-to-root)
            path = chr(ord('a') + node.val) + path
            if not node.left and not node.right:
                if path < self.result:
                    self.result = path
            dfs(node.left, path)
            dfs(node.right, path)
        
        dfs(root, "")
        return self.result

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    string result = "~";
    void dfs(TreeNode* node, string path) {
        if (!node) return;
        path = char('a' + node->val) + path;
        if (!node->left && !node->right) {
            if (path < result) result = path;
        }
        dfs(node->left, path);
        dfs(node->right, path);
    }
    string smallestFromLeaf(TreeNode* root) {
        dfs(root, "");
        return result;
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private String result = "~";
    public String smallestFromLeaf(TreeNode root) {
        dfs(root, "");
        return result;
    }
    private void dfs(TreeNode node, String path) {
        if (node == null) return;
        path = (char)('a' + node.val) + path;
        if (node.left == null && node.right == null) {
            if (path.compareTo(result) < 0) result = path;
        }
        dfs(node.left, path);
        dfs(node.right, path);
    }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string}
 */
var smallestFromLeaf = function(root) {
    let result = "~";
    function dfs(node, path) {
        if (!node) return;
        path = String.fromCharCode(97 + node.val) + path;
        if (!node.left && !node.right) {
            if (path < result) result = path;
        }
        dfs(node.left, path);
        dfs(node.right, path);
    }
    dfs(root, "");
    return result;
};

Problem Description

Given the root of a binary tree where each node contains an integer value between 0 and 25 (inclusive), representing the letters 'a' to 'z' (i.e., 0 maps to 'a', 1 to 'b', ..., 25 to 'z'), your task is to find the lexicographically smallest string that starts at a leaf of this tree and ends at the root. Each string is constructed by concatenating the characters for each node visited from the leaf up to the root. Key constraints:

Each node's value is in the range 0 to 25, mapping to lowercase English letters.
There is at least one node (the tree is non-empty).
Each string must start at a leaf and end at the root (leaf-to-root order).
Return the lexicographically smallest such string.

Thought Process

When first approaching this problem, you might think about generating all possible paths from every leaf to the root, converting each path into a string, and then comparing all of them to find the smallest one. However, generating all paths and storing them could be inefficient, especially for large trees. Instead, we can optimize by:

Traversing the tree using Depth-First Search (DFS), building the string as we go.
Whenever we reach a leaf, we check if the constructed string is smaller than our current best and update accordingly.
Since we only care about the smallest string, we do not need to store all paths, just the current best one.

This approach is both memory and time efficient, as we avoid unnecessary storage and comparisons.

Solution Approach

The solution uses a recursive DFS algorithm to traverse the tree:

Start at the root node and traverse down to every leaf.
At each node, prepend the corresponding character (from the node's value) to the current path string. We prepend because the string must be built from leaf to root.
When a leaf node is reached (both left and right children are null), compare the current path string to the smallest string found so far. If it's smaller, update the smallest string.
Recursively continue this process for both left and right children.
Return the smallest string found after traversing all paths.

Design Choices:

We use recursion for elegant tree traversal and path management.
By carrying the current path as an argument, we avoid global state except for the smallest string.
We use string comparison, which is efficient for short strings (paths cannot be longer than the tree's height).

Example Walkthrough

Example:

Suppose the tree is:

Where node values map as: 0 - 'a', 1 - 'b', 2 - 'c', 3 - 'd'.

Possible leaf-to-root paths:
- Leaf 1 (left child): 'b' (node 1) up to 'a' (root) → "ba"
- Leaf 3 (left child of 2): 'd' (node 3) to 'c' (node 2) to 'a' (root) → "dca"
Compare "ba" and "dca": "ba" is lexicographically smaller.
Thus, the answer is "ba".
During traversal, the algorithm constructs each string as it reaches a leaf and updates the result if a smaller string is found.

Time and Space Complexity

Brute-force approach:
- Time: O(N * H), where N is the number of nodes and H is the height of the tree (since each path could be up to H long, and there could be up to N leaves).
- Space: O(N * H) if all paths are stored.
Optimized DFS approach (used here):
- Time: O(N * H), since each node is visited once, and path strings are up to H in length for each leaf.
- Space: O(H) for the recursion stack and path string (since we do not store all paths).
The solution is efficient for reasonably sized trees.

Summary

This problem is elegantly solved using a recursive DFS traversal, building path strings from leaf to root and updating the smallest string as we go. By only keeping track of the current path and the best result, we avoid unnecessary storage and achieve both clarity and efficiency. The key insight is to process each path as we traverse, leveraging string comparison and recursive tree traversal for a concise solution.

AlgoMap.io

Want Help Cracking FAANG?