988. Smallest String Starting From Leaf - Explanation

1. Depth First Search

Intuition

We need to find the lexicographically smallest string that starts at a leaf and ends at the root. Since strings are built from leaf to root, we traverse the tree while building the string by prepending each node's character. When we reach a leaf, we have a complete string to compare. By exploring all paths and keeping track of the minimum string found, we get our answer.

Algorithm

Perform dfs from the root, passing the current string built so far.
At each node, prepend the corresponding character (convert node value to 'a' + value) to the current string.
If the node has both children, recursively explore both and return the minimum of the two results.
If the node has only one child, continue dfs on that child.
If the node is a leaf (no children), return the current string.
Return the minimum string found across all leaf-to-root paths.

# 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:
        def dfs(root, cur):
            if not root:
                return

            cur = chr(ord('a') + root.val) + cur
            if root.left and root.right:
                return min(
                    dfs(root.left, cur),
                    dfs(root.right, cur)
                )

            if root.right:
                return dfs(root.right, cur)
            if root.left:
                return dfs(root.left, cur)
            return cur

        return dfs(root, "")

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

2. Breadth First Search

Intuition

Instead of recursion, we can use a queue to traverse the tree level by level. Each queue entry stores a node along with the string built from the root down to that node. When we encounter a leaf, we compare its complete string with the current minimum. BFS naturally explores all paths, and we simply track the smallest leaf-to-root string found.

Algorithm

Initialize a queue with the root node and an empty string.
While the queue is not empty:
- Dequeue a node and its associated string.
- Prepend the current node's character to the string.
- If the node is a leaf, update the result if this string is smaller.
- Enqueue left and right children (if they exist) with the updated string.
Return the smallest string found.

# 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:
        q = deque([(root, "")])
        res = None

        while q:
            node, cur = q.popleft()
            cur = chr(ord('a') + node.val) + cur

            if not node.left and not node.right:
                res = min(res, cur) if res else cur

            if node.left:
                q.append((node.left, cur))
            if node.right:
                q.append((node.right, cur))

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

3. Iterative DFS

Intuition

This approach mirrors the recursive DFS but uses an explicit stack instead of the call stack. We push nodes along with their accumulated strings onto the stack. By processing nodes in LIFO order, we achieve depth-first traversal. The logic for building strings and comparing at leaves remains the same as the recursive version.

Algorithm

Initialize a stack with the root node and an empty string.
While the stack is not empty:
- Pop a node and its associated string.
- Prepend the current node's character to the string.
- If the node is a leaf, update the result if this string is smaller.
- Push right child first, then left child (so left is processed first due to LIFO).
Return the smallest string found.

# 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:
        stack = [(root, "")]
        res = None

        while stack:
            node, cur = stack.pop()
            cur = chr(ord('a') + node.val) + cur

            if not node.left and not node.right:
                res = min(res, cur) if res else cur

            if node.right:
                stack.append((node.right, cur))
            if node.left:
                stack.append((node.left, cur))

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$