Smallest String Starting From Leaf
Medium · Trees · String · Tree · Depth-First Search · Binary Tree
Problem
Each node of a binary tree holds a value from 0 to 25, standing for the letters 'a' to 'z'.
Every leaf defines a string: read the letters on the path from that leaf up to the root. Return the lexicographically smallest such string.
A string that is a proper prefix of another is the smaller one, so "ab" < "aba". A leaf is a node with no children.
Examples
Input: root = [2,0,1,3,4] Output: "bc"
The leaf-to-root strings are "dac", "eac" and "bc"; "bc" wins because "b" comes before "d" and "e".
Input: root = [0,1,1] Output: "ba"
Both leaves give "ba".
Input: root = [25,1,3,1,3,0,2] Output: "adz"
The strings are "bbz", "dbz", "adz" and "cdz". The winner sits under the larger child 3 (d), so choosing the smaller child at each step would miss it.
Constraints
- The number of nodes is in the range [1, 8500]
- 0 <= Node.val <= 25
Approaches
- Baseline: collect every leaf string, then sort — time O(n · h · log n), space O(n · h)
Follow-up
Can you prune? Only when the comparison starts at the root: reading top-down, a subtree can be skipped once its path prefix is already larger than the best answer. Reading from the leaf, no such bound exists, so every leaf must be tried. The use cases flip the order to the largest string and to reading from the root.
Related problems
Start free on Cariara · Coding problems · System design studio
