Smallest String Starting From Leaf - Pre-Order DFS

Problem: https://leetcode.com/problems/smallest-string-starting-from-leaf/description/

Given the root of a binary tree, each node has a value from 0 to 25 representing 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 1000.
    2. Each node in the tree will have a value between 0 and 25.
    The problem can actually be solved with a DFS (Depth-First-Search) and pre-order traversal:

    • If you land on a null, return and do nothing
    • Landing on a leaf, process the case checking whether this solution is better than the best
    • Call Left
    • Call Right
    Code is below, cheers, ACC.


    public class Solution
    {
     public string SmallestFromLeaf(TreeNode root)
     {
      string smallest = "";
      SmallestFromLeaf(root, "", ref smallest);
      return smallest;
     }
    
     private void SmallestFromLeaf(TreeNode node,
             string current,
             ref string smallest)
     {
      if (node == null) return;
      if (node.left == null && node.right == null)
      {
       current = ((char)(node.val + (int)'a')).ToString() + current;
       if (!String.IsNullOrEmpty(current) && (String.IsNullOrEmpty(smallest) || current.CompareTo(smallest) < 0))
       {
        smallest = current;
       }
       return;
      }
    
      SmallestFromLeaf(node.left, ((char)(node.val + (int)'a')).ToString() + current, ref smallest);
      SmallestFromLeaf(node.right, ((char)(node.val + (int)'a')).ToString() + current, ref smallest);
     }
    }
    

    Comments

    1. Nice, although I think the reason why it takes so long to execute is because of unnecessary string conversions in each invocation - it's possible and faster to compare ints instead of strings, not to mention the allocation cost. It's also possible to use a sentinel value (any int that is larger than 26) to avoid extra String.IsNullOrEmpty(smallest) checks. My initial take was using explicit stack:

      class Solution:
      def smallestFromLeaf(self, root: TreeNode) -> str:
      smallest_so_far: 'List[Tuple[int]]' = [(27,)] # sentinel larger than any lowercase letter
      def explore(node: TreeNode, stack: 'List[int]') -> None:
      stack.append(node.val)
      if not node.left and not node.right: # leaf
      smallest_so_far[0] = min(smallest_so_far[0], tuple(reversed(stack)))
      else:
      for child in (node.left, node.right):
      if child:
      explore(child, stack)
      stack.pop()

      explore(root, [])
      return "".join(chr(val + ord('a')) for val in smallest_so_far[0])

      https://gist.github.com/ttsugriy/d55bfffdeef86989c2568a0c4cd131ef

      but using implicit stack makes the solution much more concise:

      class Solution:
      def smallestFromLeaf(self, root: TreeNode) -> str:
      if not root:
      return "{" # sentinel larger than any lowercase letter
      string = chr(root.val + ord('a'))
      return string if root.left == root.right else min(self.smallestFromLeaf(root.left) + string, self.smallestFromLeaf(root.right) + string)

      https://gist.github.com/ttsugriy/8b3048ba99685bc1507abf3220870068

      Even though both solutions are in Python they are significantly faster than C# (~40ms) and use much less memory ~6.8MB :)

      ReplyDelete
    2. Yeah, totally true, there is a lot of unnecessary string conversion, thanks for pointing that out!

      ReplyDelete
      Replies
      1. with good JIT it's probably not that much of a difference, but I was just surprised to see that Python is taking less memory :)

        Delete

    Post a Comment

    Popular posts from this blog

    Count Binary Substrings

    Count Vowels Permutation: Standard DP

    Maximum Number of Balloons