NeetCode #462LC-988MediumTrees
← Back to All Problems#462 · #988 · Smallest String Starting From Leaf(从叶结点开始的最小字符串)
📌 Problem Statement & Constraints
Given the root of a binary tree where each node holds a value from 0 to 25 (mapping to
a-z), each root-to-leaf path forms a string (leaf letter first). Return the lexicographically smallest such string. Constraints: the number of nodes is in [1, 8500], 0 <= Node.val <= 25.💡 Core Algorithmic Approaches
- Build the string from the leaf upward:
chr(97 + node.val) + path. - At a leaf, compare the accumulated string with the best so far.
- The reversal (leaf first) is achieved by prepending each character as the recursion unwinds.
- Comparing strings lexicographically is what the problem asks for, so no length-based tie-break is needed.
💻 Benchmark Python3 Implementation
class Solution:
def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
self.best = None
def dfs(node: Optional[TreeNode], path: str) -> None:
if not node:
return
path = chr(97 + node.val) + path # prepend -> leaf-first order
if not node.left and not node.right:
if self.best is None or path < self.best:
self.best = path
return
dfs(node.left, path)
dfs(node.right, path)
dfs(root, "")
return self.best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * L) where L is the path length: each node prepends to a string, costing O(L).
💾 Space Complexity
O(h * L) for the strings along the recursion.
⚠️ Interview Pitfalls & Follow-ups
- Appending instead of prepending: the string would read root-first, the opposite of the required order.
- Returning the shortest string on ties: the comparison is purely lexicographic, so
path < self.bestis exactly right. - Only considering the leftmost path: all root-to-leaf paths must be compared.
- Using a list and joining at the end without reversing: the order would be wrong.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.