Hackerrank In Top 30 MAANG Interview question — Trees : Smallest String Starting From Leaf

Medium

Given the root of a binary tree, each node has a value from 0 to 25representing the letters 'a' to 'z': a value of 0 represents 'a', a value of 1 represents 'b', and so on.

Find the lexicographically smallest string that starts at a leaf of this tree and ends at the root.

(As a reminder, any shorter prefix of a string is lexicographically smaller: for example, "ab" is lexicographically smaller than "aba". A leaf of a node is a node that has no children.)

Example 1:

Input: [0,1,2,3,4,3,4]
Output: "dba"

Example 2:

Input: [25,1,3,1,3,0,2]
Output: "adz"

Example 3:

Input: [2,2,1,null,1,0,null,0]
Output: "abc"

Note:

1. The number of nodes in the given tree will be between 1 and 8500.
2. Each node in the tree will have a value between 0 and 25.

Solution

Solution is exactly like this algorithm. Try and understand the iterative part.

BST —Sum Root to Leaf Numbers

# 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: TreeNode) -> str:
        sm = ""
        stack = [(root, "")]
        
        while stack:
            node, s = stack.pop()
            
            if node:
                s =  chr(node.val+97) + s
                
                if not node.left and not node.right:
                    if s < sm or sm == "":
                        sm = s
                else:
                    stack.append((node.right, s))
                    stack.append((node.left, s))
                    
        return sm