LC988. Smallest String Starting From Leaf

# 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:
        smallest = ""
        
        def dfs(node, prev = ""):
            nonlocal smallest
 
            if not node:
                return
 
            curr = chr(ord('a') + node.val) + prev
            
            # If we're at a leaf node, we need to check and see if we have a new
            # smaller string 
            if not node.right and not node.left:
                if smallest == "":
                    smallest = curr
                elif curr < smallest:
                    smallest = curr
                
                return
            
            # If we're not yet at a leaf node, keep recursing
            if node.left:
                dfs(node.left, curr)
            
            if node.right:
                dfs(node.right, curr)
        
        dfs(root)
 
        return smallest

Complexity

Time: $O(n)$ (or $O(n^2)$ if we assume string creation/copying is slow)
Space: $O(n)$