# Written by Kash Nouroozi in June 2019

def order(node, fn):
    if node is None:
        return
    # in: LNR
    # post: LRN
    # pre: NLR
		order(node.left, fn)
    if fn(node) is True: # return early if predicate returns True
        return node
		order(node.right, fn)

Traversal

Search

# Written by Kash Nouroozi in June 2019

from collections import deque

def search(node, fn):
    plan = deque()
    plan.append(node)
    visited = {}

    def visit(node):
        if node not in visited:
            plan.append(node)
            visited.add(node)
        return fn(node)

    while plan:
        node = plan.pop() # bfs popleft()
        if visit(node):
            return node

Dynamic Programming

# Written by Kash Nouroozi for an interview with Rippling HR in June 2019

def ternary_string_possibilities(n):
    """
    ternary string is composed of a's, b's, and c's
    string can have at most 1 b
    string can have no more than 2 consecutive a's

    given a length n, calculate number of possible strings of length n
    """
    memo = {}

    def total_starting_from(state):
        if state in memo:
            return memo[state]
        running_total = 0
        has_b, trailing_a_count, size = state
        if size == n:
            return 1
        if not has_b:
            running_total += total_starting_from((True, 0, size+1))
        if trailing_a_count != 2:
            running_total += total_starting_from((has_b, trailing_a_count+1, size+1))
        running_total += total_starting_from((has_b, 0, size+1))
        memo[state] = running_total
        return running_total

    return total_starting_from((False, 0, 0))