Smallest String Starting From Leaf

How it works

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.

Steps

1. Initialize a stack with the root node and an empty string.
2. 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).
3. Return the smallest string found.

Complexity

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

Things to watch for

Building the String in the Wrong Direction

The string must be built from leaf to root, not root to leaf. This means prepending each character as you traverse down the tree. A common mistake is appending characters during traversal, which produces the reversed string. Always use cur = char + cur (prepend), not cur = cur + char (append).

Comparing Incomplete Strings at Non-Leaf Nodes

Only complete strings from leaf nodes should be compared. If you compare strings at internal nodes, you might select a prefix that leads to a suboptimal complete string. Always ensure comparisons only happen when node.left == null && node.right == null, confirming the node is truly a leaf.

Ignoring Single-Child Nodes

When a node has only one child, you must continue traversal on that child. A common bug is treating nodes with one child as leaves or skipping the single child entirely. This causes valid paths to be missed. Always check for left-only and right-only cases separately from the two-children and no-children cases.

from typing import Optional

# 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

/**
 * 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 smallestFromLeaf(TreeNode* root) {
        stack<pair<TreeNode*, string>> stk;
        stk.push({root, ""});
        string res;

        while (!stk.empty()) {
            auto [node, cur] = stk.top();stk.pop();
            cur = char('a' + node->val) + cur;

            if (!node->left && !node->right) {
                if (res.empty() || cur < res) {
                    res = cur;
                }
            }

            if (node->right) stk.push({node->right, cur});
            if (node->left) stk.push({node->left, cur});
        }
        return res;
    }
};