The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Binary Trees

Next ►
►

In the previous lesson we built generic trees where each node can have any number of children: perfect for free-form hierarchies like TaskFlow's, but with no strong mathematical properties to exploit. This lesson restricts the tree to at most two children per node, with distinguished positions (left and right), and that simple restriction opens the door to almost everything left in the module: binary search trees (06-04), AVL trees (06-05), and heaps (06-07) are all built on binary trees. Here you'll learn the BinaryNode class, the kinds of binary tree (full, complete, perfect, degenerate), the arithmetic that ties nodes to height — the key to why "O(log n)" will show up so often — and a surprising representation: a complete tree stored in a flat array.

Contents

  1. Definition: two children, each with a name of its own
  2. The BinaryNode class
  3. Kinds of binary trees: full, complete, perfect, and degenerate
  4. Binary tree arithmetic: nodes, levels, and height
  5. Array representation of a complete tree
  6. TaskFlow: a binary decision tree for classifying tasks

Definition: two children, each with a name of its own

A binary tree is a tree in which each node has at most two children, and — crucial detail — each child occupies a named position: left child or right child. A node with only a left child and a node with only a right child are different binary trees.

graph TD
    subgraph "Tree A"
        A1((5)) --> B1((3))
        A1 -.x.-> C1(( ))
    end
    subgraph "Tree B (different from A)"
        A2((5)) -.x.-> B2(( ))
        A2 --> C2((3))
    end

In the generic tree, children = [x] was simply "one child". Here the position matters, and that nuance will be pure gold in 06-04: "left = smaller, right = larger" only makes sense if left and right exist as separate concepts.

The BinaryNode class

Instead of a list of children, two named references — the same leap we made from Node to DoublyNode in module 2, but with a different meaning: there, prev/next chained things in a line; here, left/right branch.

class BinaryNode:
    """A binary tree node: a value and two positioned children."""

    def __init__(self, value):
        self.value = value
        self.left = None     # left subtree  (None = absent)
        self.right = None    # right subtree (None = absent)

And that's it: no more methods needed, because children are assigned directly. Let's build the first tree by hand:

graph TD
    R((10)) --> I((6))
    R --> D((15))
    I --> II((3))
    I --> ID((8))
    D --> DI((12))
root = BinaryNode(10)
root.left = BinaryNode(6)
root.right = BinaryNode(15)
root.left.left = BinaryNode(3)
root.left.right = BinaryNode(8)
root.right.left = BinaryNode(12)

The recursive definition from the previous lesson gets refined: a binary tree is either empty (None), or a node with a left binary tree and a right binary tree. That's why functions over binary trees almost always have this silhouette:

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

def height(node):
    """Height of the subtree. Convention: empty tree = -1, leaf = 0."""
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))

print(count(root))    # 6
print(height(root))   # 2

A detail in height: returning -1 for the empty tree makes the arithmetic work out by itself — a leaf has two None children of height -1, so its height is 1 + max(-1, -1) = 0, as it should be. And max because height is set by the longest path down to a leaf.

Kinds of binary trees: full, complete, perfect, and degenerate

Not all binary trees with the same nodes have the same shape, and shape determines performance. The four names you need to know:

Kind Definition Visual idea
Full Every node has 0 or 2 children (never exactly 1) No "half-finished arms"
Complete All levels full except possibly the last, which fills left to right with no gaps Fills like a theater, row by row
Perfect All levels completely full (all leaves at the same depth) The ideal triangle
Degenerate Every node has a single child: the tree is a chain A linked list in disguise 
graph TD
    subgraph "Full"
        L1((A)) --> L2((B))
        L1 --> L3((C))
        L2 --> L4((D))
        L2 --> L5((E))
    end
    subgraph "Complete"
        C1((A)) --> C2((B))
        C1 --> C3((C))
        C2 --> C4((D))
        C2 --> C5((E))
        C3 --> C6((F))
    end
graph TD
    subgraph "Perfect"
        P1((A)) --> P2((B))
        P1 --> P3((C))
        P2 --> P4((D))
        P2 --> P5((E))
        P3 --> P6((F))
        P3 --> P7((G))
    end
    subgraph "Degenerate"
        D1((A)) --> D2((B))
        D2 --> D3((C))
        D3 --> D4((D))
    end

Observations worth internalizing:

  • Every perfect tree is complete and full; the categories overlap.
  • Complete — filling level by level, left to right, no gaps — sounds like an arbitrary definition, but it's exactly the shape that enables the array representation of section 5, and that's why it's the shape of the heaps in 06-07.
  • Degenerate is the nightmare: structurally it's a linked list from module 2, with O(n) cost to reach the end. In 06-04 we'll see how easy it is to create one by accident, and 06-05 exists to prevent it.

Binary tree arithmetic: nodes, levels, and height

Three numeric facts, all derived from "each node has at most 2 children":

  • Level k holds at most 2^k nodes: 1 at level 0 (the root), 2 at level 1, 4 at level 2, 8 at level 3... Each level can double the previous one. (Sound familiar? In module 4, the binaries_up_to(n) exercise generated "1, 10, 11, 100..." with a queue: you were doing a level-order traversal of a perfect binary tree without knowing it. In 06-03 we'll close that circle.)
  • A tree of height h holds at most 2^(h+1) − 1 nodes: the sum 1 + 2 + 4 + ... + 2^h. A perfect tree of height 10 houses 2,047 nodes; of height 20, over two million.
  • In reverse — and this is the important count — a tree with n nodes has minimum height ⌊log₂ n⌋: to store n nodes you need at least log₂(n) levels, because fewer levels don't give you enough capacity. And maximum height n − 1 (the degenerate tree).
n nodes Minimum height (balanced) Maximum height (degenerate)
7 2 6
1,000 9 999
1,000,000 19 999,999

This table is the map of the rest of the module. Almost every operation we'll see (searching in 06-04, inserting/extracting in 06-07) costs O(height): they walk from the root downward, one node per level. If the tree is balanced, height ≈ log₂ n and the operation is logarithmic — 20 steps for a million elements, the same magic as binary search in module 1. If it's degenerate, height ≈ n and we're back to the linked list's O(n). The entire battle of 06-04 and 06-05 is keeping the height logarithmic.

Array representation of a complete tree

Surprise: a complete binary tree needs no nodes or references — it fits in a Python list. Number the nodes level by level, left to right, starting at 0, and that number is its index in the array:

graph TD
    A["10 (i=0)"] --> B["6 (i=1)"]
    A --> C["15 (i=2)"]
    B --> D["3 (i=3)"]
    B --> E["8 (i=4)"]
    C --> F["12 (i=5)"]
tree = [10, 6, 15, 3, 8, 12]

The arithmetic that replaces the references — learn it, because it's the heart of the heap in 06-07:

From the node at index i Formula
Left child 2*i + 1
Right child 2*i + 2
Parent (i - 1) // 2 
def left_child(tree, i):
    j = 2 * i + 1
    return tree[j] if j < len(tree) else None

def right_child(tree, i):
    j = 2 * i + 2
    return tree[j] if j < len(tree) else None

def parent(tree, i):
    return tree[(i - 1) // 2] if i > 0 else None

print(left_child(tree, 0))   # 6   (children of 10: indices 1 and 2)
print(right_child(tree, 1))  # 8   (children of 6: indices 3 and 4)
print(parent(tree, 5))       # 15  ((5-1)//2 = 2)

Check the formulas against the diagram: the children of index 1 are 3 and 4; those of index 2 are 5 and 6. Advantages of this representation: zero memory spent on references (compare with the two pointers per node in BinaryNode), contiguous data in memory (the cache locality of 01-05), and parent↔child navigation with one division. The fine print: it only works with no gaps, i.e., with complete trees. If the tree had a gap in the middle, you'd have to pad with None and waste slots — in a degenerate tree of 20 nodes, over a million gaps. That's why the heap of 06-07 stays always complete: so it can live in an array.

TaskFlow: a binary decision tree for classifying tasks

Where does a binary tree fit into TaskFlow, beyond preparing for 06-04? In a decision tree: each internal node is a yes/no question, left = no, right = yes, and the leaves are verdicts. Let's classify incoming tasks:

graph TD
    A{"priority == 1?"} -->|no| B{"status == blocked?"}
    A -->|yes| C{"status == blocked?"}
    B -->|no| D["Normal inbox"]
    B -->|yes| E["Review dependencies"]
    C -->|no| F["Handle NOW!"]
    C -->|yes| G["Escalate to the owner"]
def make_question(question_text, condition):
    """Internal node: stores the question and the function that evaluates it."""
    node = BinaryNode(question_text)
    node.condition = condition       # function task -> bool
    return node

# Leaves: the verdict is the value
inbox     = BinaryNode("Normal inbox")
review    = BinaryNode("Review dependencies")
handle    = BinaryNode("Handle NOW!")
escalate  = BinaryNode("Escalate to the owner")

# Internal nodes (convention: left = no, right = yes)
urgent = make_question("priority == 1?", lambda t: t["priority"] == 1)
blocked_not_urgent = make_question("blocked?", lambda t: t["status"] == "blocked")
blocked_urgent     = make_question("blocked?", lambda t: t["status"] == "blocked")

urgent.left, urgent.right = blocked_not_urgent, blocked_urgent
blocked_not_urgent.left, blocked_not_urgent.right = inbox, review
blocked_urgent.left, blocked_urgent.right = handle, escalate

def classify(node, task):
    """Walks down the tree answering questions until reaching a leaf."""
    while node.left is not None:               # leaves have no children
        if node.condition(task):
            node = node.right                  # yes -> right
        else:
            node = node.left                   # no -> left
    return node.value

t1 = {"id": "T-07", "title": "Server outage", "priority": 1, "status": "pending"}
t2 = {"id": "T-08", "title": "Update logo", "priority": 3, "status": "blocked"}
print(classify(urgent, t1))   # Handle NOW!
print(classify(urgent, t2))   # Review dependencies

Notice two things. First: classify is iterative and O(height) — it answers one question per level and descends; with a balanced tree, classifying among 2^h verdicts costs only h questions. Second: the "compare at the node and choose left or right" pattern you just wrote is, gesture for gesture, the same one we'll use to search the BST in 06-04 — only the question will change (is my key smaller than yours?).

Common Mistakes and Tips

  • Treating left and right as interchangeable. A node with only a left child and one with only a right child are different trees. From 06-04 onward, confusing them directly breaks correctness.
  • Confusing "full" and "complete". Even the English literature isn't always consistent about these terms. Stick to the definitions in the table; in this course "complete" always means "no gaps, filled level by level from left to right" — the shape of the heap.
  • Using the array representation with non-complete trees. The 2i+1/2i+2 formulas assume there are no gaps. With an arbitrary tree you'd have to insert None padding, and in the worst case (degenerate) the array grows exponentially relative to the real nodes.
  • Neglecting the empty tree height convention. Some texts give the leaf height 1 and the empty tree 0 (counting nodes instead of edges). Either works if you're consistent; in this course: empty = −1, leaf = 0.
  • Tip: when in doubt about an index formula, draw a 6-7 node tree, number it level by level, and check it by hand in 30 seconds. It's infinitely better than memorizing.

Exercises

Exercise 1: is it a full tree?

Write is_full(node) that returns True if every node in the tree has 0 or 2 children. Test it with the tree from section 2 (which is not full: node 15 has a single child) and with TaskFlow's decision tree (which is).

Exercise 2: from the array to the leaf list, without building nodes

Given a complete tree in array representation, write array_leaves(tree) that returns the list of its leaf values using only the index formulas (a node is a leaf if its left child would fall outside the array). For [10, 6, 15, 3, 8, 12] it must return [3, 8, 12].

Exercise 3: minimum levels for TaskFlow's tasks

Without running any code: TaskFlow manages 5,000 tasks and you want to store them in a binary tree. (a) What is the minimum possible height of the tree? (b) And the maximum? (c) If an operation costs O(height), how many steps is that in each case? Then verify (a) with one line of Python.

Solutions

Solution 1

def is_full(node):
    if node is None:
        return True                              # the empty tree trivially qualifies
    if (node.left is None) != (node.right is None):
        return False                             # exactly one child: not full
    return is_full(node.left) and is_full(node.right)

print(is_full(root))     # False (15 only has a left child)
print(is_full(urgent))   # True  (the decision tree)

Comment: the key line uses != between two booleans as an "exclusive or": it's False when both children exist or both are missing, and True (→ not full) when there's exactly one. And the final and short-circuits as soon as one subtree fails. A design note: a decision tree being full is no accident — a question with only one possible answer wouldn't be a question.

Solution 2

def array_leaves(tree):
    result = []
    for i in range(len(tree)):
        if 2 * i + 1 >= len(tree):       # no left child => no children => leaf
            result.append(tree[i])
    return result

print(array_leaves([10, 6, 15, 3, 8, 12]))   # [3, 8, 12]

Comment: in a complete tree there can't be a right child without a left one (the last level fills left to right), so checking 2i+1 is enough. A bonus you can verify: the first leaf is always at index len(tree) // 2 — in a 6-element array, indices 0, 1, and 2 are internal and 3, 4, and 5 are leaves. The heapify of 06-07 will exploit exactly this fact.

Solution 3

(a) The minimum height is ⌊log₂ 5000⌋ = 12 (2¹³ − 1 = 8,191 ≥ 5,000 nodes fit in 13 levels, and 2¹² − 1 = 4,095 < 5,000 proves 12 levels aren't enough). (b) The maximum is 4,999: the degenerate tree, one task hanging from another. (c) O(height) means about 12 steps in the balanced tree versus up to 4,999 in the degenerate one — more than 400 times worse with the same data.

import math
print(math.floor(math.log2(5000)))   # 12

Comment: this gap isn't theoretical: in 06-04 we'll provoke it with real code (by inserting already-sorted ids) and in 06-05 we'll measure it. Keep these numbers in your head.

Conclusion

The binary tree adds a discipline to the hierarchy of 06-01: at most two children, each with its own position. From that discipline you've extracted the BinaryNode class, the taxonomy of shapes (full, complete, perfect, degenerate), the arithmetic tying nodes to height — with the module's central conclusion: O(height) operation + balanced tree = O(log n); degenerate tree = O(n) — and the array representation with 2i+1/2i+2 indices that will reappear in the heap of 06-07. You've also written your first descent that compares at each node, with TaskFlow's decision tree. But so far we've visited nodes somewhat "on demand", without method. The next lesson brings order: the four systematic traversals of a tree — preorder, inorder, postorder, and level-order — which are to trees what the for loop is to lists, and where the queue from module 4 and that binaries_up_to exercise will finally show their true face.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2026. All rights reserved