Measuring a Tree with Recursion

The recipe for tree recursion

Almost every tree question can be answered with the same three-line recipe:

• If the node is None, return the answer for an empty tree.
• Ask the same question about the left subtree and the right subtree.
• Combine the two answers with the current node.

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

root = Node(8, Node(3, Node(1), Node(6, Node(4))), Node(10, None, Node(14)))

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

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

def total(node):
    if node is None:
        return 0
    return node.value + total(node.left) + total(node.right)

def leaves(node):
    if node is None:
        return 0
    if node.left is None and node.right is None:
        return 1
    return leaves(node.left) + leaves(node.right)

print("height:", height(root))
print("nodes: ", count(root))
print("sum:   ", total(root))
print("leaves:", leaves(root))

Output

height: 4
nodes:  7
sum:    46
leaves: 3

Each function visits every node once: O(n) time. The recursion goes as deep as the tree is tall, so it uses O(height) memory.

Tip: Mirror a tree, check if two trees are the same, find the biggest value – all follow the same recipe. Try them!