Nice warm-up.

See how it relates to detecting pangram and counting characters in a string, and counting duplicates. So much counting!

vowels = ['a', 'e', 'i', 'o', 'u']
def get_count(sentence):
    res = 0
    for c in sentence:
        if c in vowels:
            res += 1
    return res

Another straightforward-enough string question with interesting counting application examples.

from collections import defaultdict
def duplicate_count(text):
    d = defaultdict(int)
    for c in text:
        c = c.lower()
        d[c] += 1
    res = 0
    for k in d:
        if d[k] > 1:
            res += 1
    return res

These don’t need to be 3 different questions. The vocabulary (knowing what pre, in, post means) is nice, and the questions follows what I see as the “typical” recursive tree-problem skeleton.

The first one is how I think it should be solved (albeit recursively). If memory serves, doing it iteratively for infix is a bit interesting. The other two example solutions are very terse.

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None: return []
        prefix = self.preorderTraversal(root.left)
        suffix = self.preorderTraversal(root.right)
        return [root.val] + prefix + suffix

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)V

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None: return []
        return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]

Breadth-first search! Of an arbitrary (not necessarily binary) tree. Glad to have this one. At least in the python implementation it’s weird that they model null as [], it should be None, but whatever.

def tree_to_list(tree_root):
    res = []
    worklist = [tree_root]
    while worklist:
        n = worklist[0]
        worklist = worklist[1:]
        if n == []:
            continue
        res.append(n.data)
        for c in n.child_nodes:
            worklist.append(c)
    return res

This is probably the right “intro to trees” question I’ve been looking for. The previous one I’ve been doing, “print everything in a binary tree”, is a bit too clunky. For those, people get hung up on the fixation with in-order versus pre-order or whatever, and also the problems usually model it as return an array of the visited nodes; and so they want to pass that as an out-parameter or similar. Ugh!

So I like this better.

def search(n: int, root: Optional[Node]) -> bool:
    """ Determines if a value is in a binary tree (NOT bst) """
    if root is None:
        return False
    if root.value == n:
        return True
    return search(n, root.left) or search(n, root.right)