Most tree problems fit one of two recursive templates. Both consist of a base case (an empty node), recursion on the children and combining the result. Terminology and traversals are in Trees: Terminology and Traversals, search trees in BST: Insert and Search.

Two templates: heights climb up on the left, the remaining sum goes down on the right
Two templates: heights climb up on the left, the remaining sum goes down on the right

Two templates

  1. Return a value (bottom-up). The function returns the answer for a subtree, and the answer of the parent is built from the answers of its children: depth is 1 + max(left, right).
  2. Accumulate (top-down). The state goes down as a parameter (the remaining sum, bounds of a BST, the current depth) or is collected into an outer list (all paths, levels).

For the examples below a tiny helper build makes a tree from a level-order list, where None means "no node".

Maximum depth and node count (return)

python
from collections import deque

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build(values):
    """Level-order list, None means no node: [3, 9, 20, None, None, 15, 7]."""
    if not values or values[0] is None:
        return None
    root = Node(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = Node(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = Node(values[i])
            queue.append(node.right)
        i += 1
    return root

def max_depth(node):
    if node is None:
        return 0                                  # base case
    return 1 + max(max_depth(node.left), max_depth(node.right))

def count(node):
    return 0 if node is None else 1 + count(node.left) + count(node.right)

tree = build([3, 9, 20, None, None, 15, 7])
print("depth:", max_depth(tree), "nodes:", count(tree))
text
depth: 3 nodes: 5

Path sum and all paths (accumulate)

has_path_sum passes the remaining sum down and checks it at a leaf. all_paths accumulates the current path: add, recurse, undo. This is the same choose-explore-undo idea as in backtracking.

python
from collections import deque

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build(values):
    """Level-order list, None means no node: [3, 9, 20, None, None, 15, 7]."""
    if not values or values[0] is None:
        return None
    root = Node(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = Node(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = Node(values[i])
            queue.append(node.right)
        i += 1
    return root