{x}
blog image

Smallest String Starting From Leaf

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.

 

Example 1:

Input: root = [0,1,2,3,4,3,4]
Output: "dba"

Example 2:

Input: root = [25,1,3,1,3,0,2]
Output: "adz"

Example 3:

Input: root = [2,2,1,null,1,0,null,0]
Output: "abc"

 

Constraints:

  • The number of nodes in the tree is in the range [1, 8500].
  • 0 <= Node.val <= 25

Solution Explanation:

The problem asks to find the lexicographically smallest string formed by concatenating node values from a leaf node to the root of a binary tree. Each node's value represents a character ('a' to 'z').

The solution employs a Depth-First Search (DFS) approach with backtracking. The algorithm traverses the tree, building a string (path) as it goes down. When it reaches a leaf node, it reverses the path (because we're building the string from leaf to root), checks if it's lexicographically smaller than the current smallest string found (ans), and updates ans if necessary. The backtracking ensures that the algorithm explores all paths from leaves to the root.

Time Complexity Analysis:

The DFS algorithm visits each node in the tree once. Therefore, the time complexity is directly proportional to the number of nodes (N) in the tree. Hence, the time complexity is O(N). The string operations (reversal, comparison) within each node visit take constant time relative to the input size.

Space Complexity Analysis:

The space complexity is determined by two factors:

  1. Recursion Stack: The depth of the recursion stack is proportional to the height (H) of the tree. In the worst case (a skewed tree), H can be equal to N.

  2. Path String: The path string stores the current path from the root to a leaf. In the worst case, the length of the path is equal to the height (H) of the tree.

Therefore, the overall space complexity is O(H), where H is the height of the tree. In the worst case, this becomes O(N).

Code Explanation (Python):

The Python code directly implements the described algorithm:

class Solution:
    def smallestFromLeaf(self, root: TreeNode) -> str:
        ans = chr(ord('z') + 1) # Initialize ans to a lexicographically larger value
 
        def dfs(root, path):
            nonlocal ans # Access and modify the outer ans variable
            if root:
                path.append(chr(ord('a') + root.val)) # Add current node's character
                if root.left is None and root.right is None: # Leaf node reached
                    ans = min(ans, ''.join(reversed(path))) # Update ans if necessary
                dfs(root.left, path) # Recursive call for left subtree
                dfs(root.right, path) # Recursive call for right subtree
                path.pop() # Backtrack: remove current node's character
 
        dfs(root, []) # Start DFS from the root
        return ans

The other languages (Java, C++, Go) follow a similar approach, adapting the syntax and data structures to their respective languages. The core logic of the DFS with backtracking and lexicographical comparison remains consistent across all implementations.