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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Smallest String Starting From Leaf

Difficulty: Medium

Problem Description

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'. Return the lexicographically smallest string that starts at a leaf of this tree and ends at the root. A leaf of a node is a node that has no children.

Key Insights

  • Each node value corresponds to a character in the alphabet.
  • A leaf node is defined as a node without children.
  • We need to traverse the tree and construct strings from the leaves to the root.
  • The comparison of strings should be lexicographic, meaning shorter strings or those with smaller characters come first.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree. We need to visit each node once. Space Complexity: O(H), where H is the height of the tree, due to the recursion stack.

Solution

We can use Depth-First Search (DFS) to traverse the binary tree. Starting from the root, we will explore each path down to the leaves. As we traverse, we will build the string in reverse (from leaf to root) and compare the strings formed at each leaf to maintain the smallest one encountered. We will use a recursive approach to facilitate this.

Code Solutions

def smallestFromLeaf(root):
    def dfs(node, path):
        if not node:
            return
        # Add the current character to the path
        path.append(chr(node.val + ord('a')))
        
        # If it's a leaf node, compare and possibly update the result
        if not node.left and not node.right:
            # Create the string from path (reverse to get the correct order)
            candidate = ''.join(reversed(path))
            nonlocal smallest
            if smallest is None or candidate < smallest:
                smallest = candidate
        
        # Continue the DFS traversal
        dfs(node.left, path)
        dfs(node.right, path)
        
        # Backtrack
        path.pop()
    
    smallest = None
    dfs(root, [])
    return smallest
← Back to All Questions