⚡Flashcard Drill➔
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

  1. Build the string from the leaf upward: chr(97 + node.val) + path.
  2. At a leaf, compare the accumulated string with the best so far.
  3. The reversal (leaf first) is achieved by prepending each character as the recursion unwinds.
  4. 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.best is 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems