Taro Logo

Smallest String Starting From Leaf

Medium
Google logo
Google
Topics:
TreesRecursionStrings

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.

Solution


Naive Approach

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).

  1. DFS Traversal: Start DFS from the root. At each node, append the corresponding character (based on node.val) to the current path.
  2. Leaf Node Check: When a leaf node is reached, reverse the path to form the string from leaf to root.
  3. Lexicographical Comparison: Compare the current string with the smallest string found so far. Update if necessary.

Code (Python)

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

Time Complexity

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.

Space Complexity

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.

Optimal Approach

The optimal approach is similar to the naive approach but optimized to minimize unnecessary comparisons.

  1. Reverse Path Construction: As we traverse down the tree, we prepend the character to the path string.
  2. Leaf Node Check: When a leaf node is encountered, we have the reversed string (leaf to root).
  3. Lexicographical Comparison: Keep track of the smallest string seen so far and update it when a smaller string is found.

Code (Python)

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, "")

Time Complexity

O(N), where N is the number of nodes in the tree. We visit each node once.

Space Complexity

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.

Edge Cases

  • Empty Tree: If the root is None, return an empty string.
  • Single Node Tree: If the tree contains only the root node, return the string representation of that node's value.
  • Unbalanced Tree: The algorithm should work correctly regardless of the tree's balance.