Recursive subtree summaries

What is a binary tree?

A tree connects nodes in a hierarchy. The root is its starting node. A child is directly below its parent; a leaf has no children. A binary tree allows at most two children per node, called left and right. Traversal means visiting its nodes in a defined order.

Example: A root containing 8 can have a left child 4 and a right child 12. A binary tree does not automatically keep smaller values on the left: that extra rule belongs to a binary search tree.

Helpful before this chapter

If these ideas are new, begin with:

Queues and deques Recursion

Understand the idea

A recursive subtree summary should be small and sufficient for its parent. Height, size, balance, and diameter can be composed bottom-up without retraversing each child subtree.

Work through an example

At node 2, child heights 0 and 0 give height 1. At root 4, heights 1 and 0 give height 2; a path through root has 1+0+2=3 edges.

Time and space complexity

O(n) time/O(h) stack for one combined pass.

Why it works

Each return is the correct summary for exactly that subtree.

Common mistakes

Recomputing heights at every node can be O(n²).
Diameter may lie entirely inside one child subtree.

Chapter lab · Python implementation

A tree gives each non-root node one parent and contains no cycles. Our binary-tree lab combines inorder traversal, subtree height, and explicit-null serialization. Height counts edges here: empty=-1, leaf=0. Some practice problems count nodes instead; translate the convention rather than changing the recurrence blindly.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

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

def inorder(node):
    if node is None: return []
    return inorder(node.left)+[node.value]+inorder(node.right)

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

def serialize(node):
    tokens=[]
    def visit(n):
        if n is None:
            tokens.append(None); return
        tokens.append(n.value)
        visit(n.left); visit(n.right)
    visit(node)
    return tokens

def deserialize(tokens):
    stream=iter(tokens)
    def build():
        value=next(stream)
        if value is None: return None
        return Node(value,build(),build())
    root=build()
    sentinel=object()
    if next(stream,sentinel) is not sentinel:
        raise ValueError('extra tokens')
    return root

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

root=Node(4,Node(2,Node(1),Node(3)),Node(6))
assert inorder(root)==[1,2,3,4,6]
assert height(root)==2 and height(None)==-1
assert serialize(deserialize(serialize(root)))==serialize(root)
assert serialize(None)==[None]

CHECK YOUR UNDERSTANDING