Smallest string from leaf node

You are given the root of a binary tree where each node has a value in the range [0, 25] representing the letters ‘a’ to ‘z’.

Return the lexicographically smallest string that starts at a leaf of this tree and ends at the root.

As a reminder, any shorter prefix of a string is lexicographically smaller.

For example, “ab” is lexicographically smaller than “aba”. A leaf of a node is a node that has no children.

leaf_to_root

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def smallestFromLeaf(root):
    def dfs(node, path):
        if not node:
            return

        # Add current node's value to the path
        path.append(chr(ord('a') + node.val))  # ord('a')=97

        if not node.left and not node.right:
            # If this is a leaf node, compare the path with the smallest string found so far
            nonlocal smallest
            current_str = ''.join(reversed(path))
            if not smallest or current_str < smallest:  # Unicode(ASCII) value compare
                smallest = current_str

        # Recursively traverse left and right subtrees
        dfs(node.left, path)
        dfs(node.right, path)

        # Backtrack: remove current node's value from the path
        path.pop()

    smallest = None
    dfs(root, [])
    return smallest


# Example usage:
# Create the binary tree
root = TreeNode(25)
root.left = TreeNode(1)
root.right = TreeNode(3)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
root.right.left = TreeNode(0)
root.right.right = TreeNode(2)

#      25
#   1      3
# 1   3  0   2

# Find the lexicographically smallest string
result = smallestFromLeaf(root)
print("Lexicographically smallest string from leaf to root:", result)
# Lexicographically smallest string from leaf to root: adz