We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Smallest String Starting From Leaf

Number: 1030

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a binary tree where each node's value is in the range [0, 25] (each representing a lowercase letter from 'a' to 'z'), return the lexicographically smallest string that starts at a leaf and ends at the root. Each string is built by concatenating the characters corresponding to the node values from leaf to root.

Key Insights

  • Use a depth-first search (DFS) to traverse the tree.
  • Build the path by prepending the character of the current node; this naturally forms the string from leaf to root.
  • At every leaf node, compare the constructed string with the smallest string found so far.
  • Use a placeholder value like "~" (which is lexicographically larger than any lowercase letter) to initialize the smallest string.
  • Edge Case: Trees with only a single node.

Space and Time Complexity

Time Complexity: O(N^2) in the worst case, due to the cost of string concatenation when the tree is skewed. Space Complexity: O(N) due to the recursion stack and the space required to maintain the current path.

Solution

We employ a depth-first search to traverse the binary tree starting from the root. As we traverse, we build the path string by prepending the current node’s character so that at the leaf, the string is in the correct order (leaf to root). When a leaf is encountered, we compare the formed string with the smallest string found so far, updating our record if needed. The DFS ensures every leaf is visited with the correct accumulated path. Key data structures include recursion for DFS and a string to maintain the path.

Code Solutions

# Python solution:
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:
        # Use '~' as the initial smallest value because it is higher than any lowercase letter.
        self.smallest = "~"
        
        def dfs(node, path):
            if not node:
                return
            # Prepend the current node's character to the path (building the string from leaf to root).
            new_path = chr(node.val + ord('a')) + path
            # If we've reached a leaf node, compare and update the smallest string.
            if not node.left and not node.right:
                if new_path < self.smallest:
                    self.smallest = new_path
                return
            # Recurse through left and right children.
            dfs(node.left, new_path)
            dfs(node.right, new_path)
        
        dfs(root, "")
        return self.smallest
← Back to All Questions