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. A leaf of a node is a node that has no children.
For example, consider the following binary tree:
0
/ \
1 2
/ \ / \
3 4 3 4
Represented as root = [0,1,2,3,4,3,4]
, the output should be "dba".
As another example:
25
/ \
1 3
/ \ / \
1 3 0 2
Represented as root = [25,1,3,1,3,0,2]
, the output should be "adz".
Write a function that takes the root of a binary tree as input and returns the lexicographically smallest string from a leaf to the root.
The most straightforward approach is to traverse all possible paths from the leaves to the root, construct the corresponding strings, and then compare them lexicographically to find the smallest one. This can be done using Depth-First Search (DFS).
node.val
) to the current path.class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def smallestFromLeaf(root: TreeNode) -> str:
def dfs(node, path):
nonlocal smallest_str
if not node:
return
path = chr(node.val + ord('a')) + path
if not node.left and not node.right:
if not smallest_str or path < smallest_str:
smallest_str = path
return
dfs(node.left, path)
dfs(node.right, path)
smallest_str = ""
dfs(root, "")
return smallest_str
O(N * L), where N is the number of nodes and L is the average length of the path from a leaf to the root. In the worst case, L can be N if the tree is a skewed tree.
O(H), where H is the height of the tree, due to the recursion stack. In the worst-case (skewed tree), H can be N, leading to O(N) space complexity.
The optimal approach is similar to the naive approach but optimized to minimize unnecessary comparisons.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def smallestFromLeaf(root: TreeNode) -> str:
def dfs(node, path):
if not node:
return "~" # Return a large string
path = chr(node.val + ord('a')) + path
if not node.left and not node.right:
return path
left_str = dfs(node.left, path)
right_str = dfs(node.right, path)
return min(left_str, right_str)
return dfs(root, "")
O(N), where N is the number of nodes in the tree. We visit each node once.
O(H), where H is the height of the tree, due to the recursion stack. In the worst case (skewed tree), H can be N, leading to O(N) space complexity.
None
, return an empty string.