Problem of The Day: Smallest String Starting From Leaf

Problem Statement

Intuition

My initial thoughts are to traverse the binary tree and keep track of the paths from the root to each leaf node. Then, I can compare these paths to find the smallest lexicographically sorted path.

Approach

I’ll use depth-first search (DFS) to traverse the tree and maintain the current path from the root to the current node. When I reach a leaf node, I’ll compare its path with the current smallest path found so far. If it’s smaller, I’ll update the smallest path. Finally, I’ll convert the smallest path to its corresponding characters and return it.

Complexity

• Time complexity: O(n) where n is number nodes in the binary tree

• Space complexity: O(h) where h is the heigh of the tree

Code

# Definition for a binary tree node.
# 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: Optional[TreeNode]) -> str:
        res = []
        def dfs(root, curr):
            nonlocal res
            if not root:
                return
            if not root.left and not root.right:
                curr.append(root.val)
                if not res:
                    res = curr[:]
                else:
                    a = list(reversed(res))
                    b = list(reversed(curr))
                    for i in range(max(len(a), len(b))):
                        x = a[i] if i < len(a) else float('-inf')
                        y = b[i] if i < len(b) else float('-inf')
                        if x > y:
                            res = curr[:]
                            break
                        elif x < y:
                            break

                return
            dfs(root.left, curr + [root.val])
            dfs(root.right, curr + [root.val])

        dfs(root, [])
        res.reverse()
        return ''.join([chr(x + ord('a')) for x in res])

Editorial Solution

DFS

class Solution:
    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
        self.smallest_string = ""
        self.dfs(root, "")
        return self.smallest_string

    # Helper function to find the lexicographically smallest string
    def dfs(self, root, current_string):
        # If the current node is NULL, return
        if not root:
            return

        # Construct the current string by appending
        # the character corresponding to the node's value
        current_string = chr(root.val + ord('a')) + current_string

        # If the current node is a leaf node
        if not root.left and not root.right:
            # If the current string is smaller than the result
            # or if the result is empty
            if not self.smallest_string or self.smallest_string > current_string:
                self.smallest_string = current_string

        # Recursively traverse the left subtree
        if root.left:
            self.dfs(root.left, current_string)

        # Recursively traverse the right subtree
        if root.right:
            self.dfs(root.right, current_string)

• Time: O(n * n) where n is the length of the resulting string
• Space: O(n * n)

BFS

class Solution:
    def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
        smallest_string = ""
        node_queue = deque()

        # Add root node to deque along with its value converted to a character
        node_queue.append([root, chr(root.val + ord('a'))])

        # Perform BFS traversal until deque is empty
        while node_queue:
            # Pop the leftmost node and its corresponding string from deque
            node, current_string = node_queue.popleft()

            # If current node is a leaf node
            if not node.left and not node.right:
                # Update smallest_string if it's empty or current string is smaller
                smallest_string = min(smallest_string, current_string) if smallest_string else current_string

            # If current node has a left child, append it to deque
            if node.left:
                node_queue.append([node.left, chr(node.left.val + ord('a')) + current_string])

            # If current node has a right child, append it to deque
            if node.right:
                node_queue.append([node.right, chr(node.right.val + ord('a')) + current_string])

        return smallest_string