Trees and Binary Trees

Trees are one of the most important non-linear data structures: filesystem directory hierarchies, the HTML/XML DOM, database indexes (B-trees/B+trees), and org charts are all trees at their core. This article covers the core concepts and properties of trees and binary trees, then implements a binary tree in Python along with its four traversal orders.

Basic Tree Concepts

A tree is a collection of n (n ≥ 0) elements: when n = 0 it’s called an empty tree; otherwise there is exactly one special element with no predecessor, called the root, and the remaining elements are partitioned into disjoint sets, each of which is itself a tree — called a subtree of the original. This is a recursive definition, and it’s also the theoretical basis for implementing traversal algorithms recursively later on.

Common terminology:

Key properties of trees: a unique root, disjoint subtrees, every node except the root has exactly one parent, and leaf nodes have no children.

Binary Trees

A binary tree is an ordered tree in which every node has at most two subtrees — even if a node has only one subtree, you must still specify whether it’s the left or the right subtree; unlike a general tree, the children can’t be arranged arbitrarily.

Basic Forms and Special Binary Trees

A binary tree has five basic forms: empty, root only, root with only a left subtree, root with only a right subtree, and root with both. There are also a few named special forms:

• Skewed tree: every node has only a left subtree (left-skewed) or only a right subtree (right-skewed) — this degenerates into a linked list.
• Full binary tree: every branch node has both a left and a right subtree, and all leaf nodes sit on the same bottom level. A full binary tree of depth k has exactly 2^k - 1 nodes.
• Complete binary tree: at depth k, levels 1 through k-1 are completely filled, and the nodes on level k are all packed to the left. Every full binary tree is a complete binary tree, but not vice versa.

Properties of Binary Trees

• Property 1: level i of a binary tree has at most 2^(i-1) nodes (i ≥ 1).
• Property 2: a binary tree of depth k has at most 2^k - 1 nodes (k ≥ 1).
• Property 3: for any binary tree, if n0 is the number of leaf nodes and n2 is the number of nodes with degree 2, then n0 = n2 + 1.
• Property 4: a complete binary tree with n nodes has depth ⌊log₂ n⌋ + 1 (in Python: math.floor(math.log2(n)) + 1).
• Property 5: if a complete binary tree is numbered level by level starting from 1, node i’s parent is i // 2, its left child is 2i, and its right child is 2i + 1 — this is exactly the theoretical basis for implementing complete-binary-tree structures like heaps with an array instead of a linked structure.

Traversing a Binary Tree

Traversal means visiting every node in a tree exactly once according to some rule, converting the tree’s hierarchical structure into a linear sequence. Let D be the root, L the left subtree, and R the right subtree:

• Level-order traversal (breadth-first): starting from the first level, visit nodes level by level, left to right.
• Preorder traversal, DLR: root → left subtree → right subtree, recursively, with each subtree following the same root-first rule.
• Inorder traversal, LDR: left subtree → root → right subtree.
• Postorder traversal, LRD: left subtree → right subtree → root.

Preorder, inorder, and postorder are all depth-first traversals, and they’re a natural fit for recursion; level-order traversal is breadth-first and is typically implemented iteratively with a queue.

Implementing a Binary Tree in Python

Take the following binary tree as an example:

        A
       / \
      B   C
     / \  / \
    D  E F   G

from collections import deque
from dataclasses import dataclass


@dataclass
class TreeNode:
    value: str
    left: "TreeNode | None" = None
    right: "TreeNode | None" = None


# Build the example tree
root = TreeNode("A",
    left=TreeNode("B", left=TreeNode("D"), right=TreeNode("E")),
    right=TreeNode("C", left=TreeNode("F"), right=TreeNode("G")),
)

Preorder / Inorder / Postorder: Recursive Implementation

def preorder(node: TreeNode | None) -> list[str]:
    """Preorder traversal, DLR: root -> left -> right."""
    if node is None:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)


def inorder(node: TreeNode | None) -> list[str]:
    """Inorder traversal, LDR: left -> root -> right."""
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)


def postorder(node: TreeNode | None) -> list[str]:
    """Postorder traversal, LRD: left -> right -> root."""
    if node is None:
        return []
    return postorder(node.left) + postorder(node.right) + [node.value]


print("preorder:", preorder(root))    # ['A', 'B', 'D', 'E', 'C', 'F', 'G']
print("inorder:", inorder(root))      # ['D', 'B', 'E', 'A', 'F', 'C', 'G']
print("postorder:", postorder(root))  # ['D', 'E', 'B', 'F', 'G', 'C', 'A']

Level-Order Traversal: Iterative with a Queue

Level-order traversal has no natural recursive structure — using collections.deque as a FIFO queue is the more direct approach:

def level_order(root: TreeNode | None) -> list[str]:
    """Level-order traversal: breadth-first search using a queue."""
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result


print("level-order:", level_order(root))   # ['A', 'B', 'C', 'D', 'E', 'F', 'G']