988. Smallest String Starting From Leaf

How to solve Smallest String Starting From Leaf (LeetCode 988): the approach in brief

The problem

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

Pattern

Smallest String Starting From Leaf is a Tree Traversal Patterns (DFS & BFS) problem, in the Recursive Preorder Traversal subpattern. The pattern covers preorder, inorder, level order traversal, LCA, and serialization

Master preorder traversal for tree construction, inversion, and path problems. Visit root before children.

Approach outline

1. Consider using a depth-first search (DFS) traversal to explore all paths from root to leaves.
2. Since the string must start from a leaf and end at the root, think about how to build the string in reverse order during traversal.
3. At each leaf node, you can form a candidate string; keep track of the lexicographically smallest string found so far.

Complexity

The reference solution runs in O(n + l * h) time and O(h) space.

Asked at

Smallest String Starting From Leaf has been reported in interviews at Google.