#988

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Smallest String Starting From Leaf

Determine the lexicographically smallest string from a leaf to root using binary-tree traversal and careful state tracking.

string backtracking tree depth first search binary tree

Problem Statement

Given the root of a binary tree where each node's value is an integer from 0 to 25 representing letters 'a' to 'z', construct strings by following paths from any leaf node up to the root. Return the lexicographically smallest string among all leaf-to-root paths.

A string is considered lexicographically smaller if it would appear first in dictionary order. For example, shorter prefixes take precedence over longer strings with the same starting sequence. The binary-tree traversal must correctly handle all branches and leaf paths to determine the minimal string.

Examples

Example 1

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

Output: "dba"

Example details omitted.

Example 2

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

Output: "adz"

Example details omitted.

Example 3

Input: root = [2,2,1,null,1,0,null,0]

Output: "abc"

Example details omitted.

Constraints

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

Solution Approach

DFS Traversal with Path Accumulation

Perform a depth-first search starting from the root, appending the current node's character to a path string. When a leaf node is reached, reverse the accumulated path to get the leaf-to-root string and compare it with the current minimum.

Backtracking to Explore All Paths

After visiting each child node, backtrack by removing the last character added to the path string. This ensures that sibling paths are evaluated independently without corrupting the accumulated string.

Lexicographical Comparison at Leaves

At each leaf node, compare the reversed path string with the current smallest string. Update the result if the new string is smaller. This guarantees that the final answer represents the globally smallest string across all leaf-to-root paths.

Complexity Analysis

Metric	Value
Time	O(n \cdot n)
Space	O(n \cdot n)

The algorithm visits each node once, building a string of length up to the tree height n along each path. Each leaf comparison involves a string of size up to n, resulting in O(n * n) time complexity. Space complexity is also O(n * n) due to storing path strings during DFS traversal.

What Interviewers Usually Probe

Check if the candidate correctly reverses paths from leaf to root before comparison.
Observe if the candidate uses backtracking to manage path state efficiently.
Notice whether the solution handles lexicographical comparison accurately at each leaf.

Common Pitfalls or Variants

Common pitfalls

Failing to reverse the path string before comparing leaf-to-root strings, yielding incorrect lexicographical order.
Modifying a shared path string without proper backtracking, causing sibling path evaluation errors.
Comparing incomplete paths or intermediate nodes instead of strictly leaf-to-root paths.

Follow-up variants

Compute the largest string from leaf to root using the same DFS and backtracking framework.
Return the smallest string starting from a specific leaf instead of all leaves, requiring targeted path tracking.
Handle n-ary trees instead of binary trees, adapting DFS and path management to multiple children.

FAQ

What is the main idea behind Smallest String Starting From Leaf?

Use DFS to traverse all leaf-to-root paths, reverse the path strings, and compare lexicographically to find the smallest.

Why is backtracking necessary in this problem?

Backtracking prevents the current path string from contaminating sibling paths, ensuring accurate leaf-to-root comparisons.

How do we handle lexicographical comparisons efficiently?

Reverse the accumulated path at each leaf and compare strings directly to maintain the smallest result found so far.

What is the time and space complexity?

Both time and space complexity are O(n * n), with n being the number of nodes, due to path accumulation and comparisons.

Can this approach be adapted to n-ary trees?

Yes, the DFS and backtracking framework works for n-ary trees by iterating through all children at each node.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

# 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: TreeNode) -> str:
        ans = chr(ord('z') + 1)

        def dfs(root, path):
            nonlocal ans
            if root:
                path.append(chr(ord('a') + root.val))
                if root.left is None and root.right is None:
                    ans = min(ans, ''.join(reversed(path)))
                dfs(root.left, path)
                dfs(root.right, path)
                path.pop()

        dfs(root, [])
        return ans

Continue Practicing

#257 binary tree paths #1028 recover a tree from preorder traversal #606 construct string from binary tree