Domain 2MediumMEDIUM

Smallest String Starting From Leaf

LeetCode problem 988: Smallest String Starting From Leaf (medium).

Domain: medium•Updated: 2026-09-05
#Tree#Depth-first Search

Problem Breakdown

Input: The root node of a binary tree where each integer value (0-25) maps to characters ‘a’-‘z’.
Output: A single string representing the lexicographically smallest path from any leaf node up to the root.

Key Constraints & Logic:

  1. Path Direction: Unlike standard DFS which goes Root → Leaf, this problem requires constructing strings in reverse order (Leaf → Root).
  2. Lexicographical Order: We must compare full paths formed by different leaves. Standard string comparison rules apply ("ab" < "aba"), meaning shorter prefixes are smaller if they match up to the length of the prefix.
  3. Edge Cases: A single-node tree counts as a leaf (root is its own parent). Skewed trees can lead to deep recursion, but Python’s default limit handles ~1000 depth; for deeper skewed inputs (N=8500N=8500), we rely on system stack limits or iterative DFS if strictly necessary. However, standard recursive solution fits within typical interview time limits given the constraints and operations per node are constant overhead plus string ops at leaves.

Intuition

Brute Force: Traverse every path from root to leaf, store each complete Leaf→Root string in a list, then sort or find min at the end. This involves creating many intermediate strings during traversal (O(N2)O(N^2) worst-case for skewed trees due to repeated concatenation) and sorting/comparing them all later.

Key Insight: We can maintain the global minimum string found so far as we traverse. Instead of storing every path, whenever we hit a leaf node, we construct that specific candidate string (Leaf→Root order), compare it against our current global best (min_s), and update min_s if this new one is smaller. This avoids sorting at the end and keeps memory usage proportional to tree height rather than total paths stored simultaneously.

Optimal Approach: Use Depth-First Search (DFS). Pass a mutable list of characters down the recursion stack to avoid repeated string concatenation overhead during traversal. At each leaf, reverse this accumulated path, join it into a string, compare with min_s, and backtrack by popping from the list before returning up the tree.

Approach

  1. Initialize a class attribute or closure variable self.min_s as None. This will hold our current best answer.
  2. Define a recursive helper function dfs(node, path):
    • Base Case: If node is null (shouldn’t happen with valid input logic inside recursion), return immediately.
    • State Update: Append the character corresponding to node.val to our current traversal list (path). This represents Root→Leaf accumulation so far.
    • Check Leaf: Determine if current node has no children. If true, it is a leaf.
      • Construct candidate string: Reverse the accumulated path (since we need Leaf→Root) and join into a string.
      • Update self.min_s: If min_s doesn’t exist or new candidate < existing min_s, update min_s.
    • Recurse: Call DFS on left child, then right child with the updated path list.
    • Backtrack: Pop from the path list after returning to ensure memory efficiency and correct state for other branches (though in Python lists are passed by reference, we must manage modification carefully or pass copies; popping is cleaner).

Complexity Analysis

  • Time Complexity: O(N⋅L)O(N \cdot L) where NN is number of nodes and LL is the maximum depth. In a skewed tree, string construction at leaves dominates. However, since we only join strings for leaf nodes (at most N/2+1N/2 + 1) and compare them, it performs well within limits (8500×avg_depth8500 \times \text{avg\_depth}).
  • Space Complexity: O(H)O(H) where HH is the height of the tree. This accounts for recursion stack depth plus the space required to store the current path list during traversal (which grows with depth) and the result string storage.

Solution

class Solution:
    def smallestFromLeaf(self, root):
        self.min_s = None
        
        # Helper function to traverse tree
        def dfs(node, path_list):
            if not node:
                return
            
            # Convert value 0-25 to char 'a'-'z' and append to current path list.
            # We accumulate Root -> Leaf order here for efficiency (O(1) appends).
            val_char = chr(ord('a') + node.val) 
            path_list.append(val_char)
            
            is_leaf = not node.left and not node.right
            
            if is_leaf:
                # Construct candidate string in correct direction (Leaf -> Root)
                # Reverse the list to get Leaf at index 0, then join.
                current_candidate = "".join(path_list[::-1])
                
                # Update global minimum found so far
                if self.min_s is None or current_candidate < self.min_s:
                    self.min_s = current_candidate
            
            dfs(node.left, path_list)
            dfs(node.right, path_list)
            
            # Backtrack to restore state for other branches (remove last added char)
            path_list.pop()

        if root:
            dfs(root, [])
        
        return self.min_s or ""

Edge Cases Handled