5.1 Binary Tree Structure and Recursion

Prerequisites: Introduction to Recursion, about 25 minutes. This section first helps you understand nodes, edges, depth, and height, then guides you through writing count, height calculation, and standard value lookup using recursive contracts.

How Nodes Form a Tree

A node stores a value and two child links, left and right. A null link means that position has no child. A lone left child and a lone right child form different shapes.

              1             depth 0
            /   \
           2     3          depth 1
          / \     \
         4   5     6        depth 2

This is a binary tree because each node has at most two children. The values in the diagram have no implied ordering: 2 being to the left of 1 does not mean that 2 must be less than 1. A binary search tree adds ordering constraints on subtree keys. Here we start with an ordinary binary tree without that ordering.

A non-empty tree has a root. Except for the root, each node has exactly one parent, so a non-empty tree with n nodes has n - 1 parent-child edges. Nodes cannot retrace their path back to ancestors via child links, or else the structure would form a cycle and cease to be a tree.

Terminology and Boundaries

Term	This page defines
root	the starting point with no parent node; in the example, it is 1
leaf	both left and right children are null; examples are 4, 5, 6
Internal node	A node with at least one child; the root can also be an internal node
Edge	A parent-child link
path	a sequence of nodes connected by edges
Ancestor/Descendant	Node above/below a given node
Subtree	A node together with all of its descendants
depth	the number of edges from the root to the node; root depth is 0
height	the number of edges from this node to the farthest leaf; leaf height is 0

"An internal node is neither a root nor a leaf" is not a universal definition. If a root has children, it is also an internal node.

Height is typically counted in two ways: by the number of edges or by the number of nodes. This page uses edge count, so leaf height is 0; to make the recursive formula height(node) = 1 + max(...) valid for leaves, the code defines the height of an empty tree as -1. Always verify the convention when switching textbooks, as the algorithm itself remains unchanged.

Structural Recursion

The definition of a binary tree is inherently recursive: a tree is either empty or consists of a root, a left subtree, and a right subtree. When writing a recursive function, you only need to answer three questions:

1. What does the function return for an empty tree?
2. What promises does the function make to the left and right subtrees?
3. How does the current node merge two child results?

The following program constructs a sample tree and implements node counting, height calculation by edge, and standard value lookup. Here, contains_value does not use key ordering, so in the worst case it may need to visit all nodes.

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

def build_sample_tree():
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.right = TreeNode(6)
    return root

def count_nodes(root):
    if root is None:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

def tree_height_edges(root):
    """Calculate height by edge count: -1 for an empty tree, 0 for a leaf."""
    if root is None:
        return -1
    return 1 + max(
        tree_height_edges(root.left),
        tree_height_edges(root.right),
    )

def contains_value(root, target):
    if root is None:
        return False
    if root.value == target:
        return True
    return (
        contains_value(root.left, target)
        or contains_value(root.right, target)
    )

sample = build_sample_tree()
assert count_nodes(None) == 0
assert count_nodes(sample) == 6
assert tree_height_edges(None) == -1
assert tree_height_edges(TreeNode(9)) == 0
assert tree_height_edges(sample) == 2
assert contains_value(sample, 5)
assert not contains_value(sample, 99)

Unpack count_nodes

An empty tree has 0 nodes. The number of nodes in a non-empty tree equals:

1 for the current root + left subtree node count + right subtree node count

You don't need to mentally unfold all the calls. Treat the recursive function as a contract for a subtree: "Give me a subtree, and I'll return the number of nodes in it." The current level only needs to add 1.

Unpack tree_height_edges

An empty tree returns -1; both empty children of a leaf return -1, so the leaf height is 1 + max(-1, -1) = 0. For any internal node, the taller subtree determines the position of the farthest leaf.

Unpack contains_value

A normal binary tree has no order to enable pruning. When the current node doesn't match, both left and right subtrees might contain the target; short-circuit evaluation only skips the right subtree if the left one already found it. The worst-case time remains O(n).

Shapes outnumber names

Binary trees can have many different shapes:

• In a full binary tree, every internal node has exactly two children.
• In a perfect binary tree, all internal nodes have exactly two children, and all leaves are at the same depth.
• A complete binary tree is full except possibly for the last level, which is filled from left to right.
• Each node in a chain tree has at most one child.
• The specific definition of balance depends on the data structure; AVL trees and red-black trees use different constraints.

This page follows NIST’s distinction between full/proper trees and perfect trees. Terminology varies: when another source says “full,” check whether it also requires equal leaf depths. Complete trees use the left-filled last-level rule.

These shapes affect height and storage. A chain of n nodes has height n - 1. A perfect tree satisfies n = 2^(h+1) - 1, hence h = log₂(n+1) - 1.

Recursion Time and Space

count_nodes, tree_height_edges, and in the worst case contains_value each visit every node once, taking Θ(n) time when node visits and comparisons have fixed cost.

For a nonempty tree, the call stack holds a root-to-current-node path, using O(h + 1) space. The extra 1 includes a leaf of height 0. An empty-tree call still uses constant space:

• When height is logarithmic, stack space is O(log n).
• The stack depth of a chained tree is O(n).

Python's recursion limit is determined by the interpreter configuration and the platform. You can use sys.getrecursionlimit() to check the current value, but don't treat it as a safe capacity, and don't rely solely on increasing the limit to handle untrusted deep trees. Iterative traversal replaces an implicit call stack with an explicit container and may still require O(h + 1) space, yet avoids dependency on recursion depth.

Common Mistakes

Treat empty links as nodes

Accessing root.left without handling root is None will trigger an attribute error. Recursive functions typically start with an empty tree base case.

Mixed-up Height Definition

The height is counted by nodes, but the formula explains it by edges, leading to a potential off-by-one error. Note in the function comment how an empty tree and a leaf differ in height.

Whenever you see left and right children, assume the tree is ordered

Left and right describe position, not key ordering. A regular binary tree must check both sides to find a value; a BST can go only one way.

Use a shared default list to collect results

Python's def walk(node, result=[]) reuses the same list across multiple calls. Use None as the default and explicitly create a list when the argument is None, or let each outer call create a result and pass it to a helper.

Input might not be a tree

If an object graph contains cycles or multiple parent nodes, recursion might result in repeated visits or infinite loops. When handling data constructed externally, a set of object identities can detect duplicate nodes.

Structural Operations at a Glance

Task	Common Patterns	Time	Auxiliary Space
Node Count	Post-order Merge	O(n)	O(h + 1)
Compute height	Post-order max value	O(n)	O(h + 1)
Determine if a regular tree contains a value	DFS/BFS	O(n)	DFS O(h + 1), BFS O(w)
Copy tree	Create node first in preorder, then copy subtrees	O(n)	O(h + 1)
Compare two trees	Synchronize recursive left and right subtrees	O(n)	O(h + 1)

h counts height in edges and w is maximum level width; empty-tree operations take constant work. The copy row excludes the new tree: its nodes require another Θ(n) space, and deep-copying payloads adds its own cost. For comparing two trees, n and h may denote the larger input size and height; comparison may stop early. Shared children or cycles require analysis as an object graph.

Hands-on Dissecting Structural Recursion

1. Label each node in the sample tree with its depth and height.
2. Move node 6 to the left of node 5, then recalculate the root height.
3. Write sum_values(root), first providing the return value for an empty tree and the merge formula.
4. Write same_shape(a, b) to compare structures, not values.
5. Rewrite contains_value using iterative DFS, and compare its explicit stack with recursive call stack.

After Understanding the Tree Structure

A binary tree only restricts "each node having at most two children" and does not automatically include sorting or balancing. When writing recursive structures, first define the base case for an empty tree, then trust that the left and right subtrees will fulfill the same agreement, with the current level merely responsible for combining. Time complexity typically depends on the number of nodes visited, while the call stack depth depends on the tree height; a long chain can push O(h + 1) all the way to O(n).

Now you can see the shape of the tree. The next section adds strict left-right ordering to the key, moving into Binary Search Tree Insertion, Deletion, and Search; subsequently, we'll compare Recursive, Explicit Stack, and Queue-Based Tree Traversals.