Introduction to Binary Trees

You're building a file system. Folders contain files and other folders. Each folder can have many children. But what if you want to organize data where each node has at most two children? That's a binary tree.

Think of a decision tree. At each step, you have two choices: yes or no, left or right. Binary trees model this naturally.

What's a Binary Tree?

A hierarchical structure. Each node has:

Data (the value)
Pointer to left child (or null)
Pointer to right child (or null)

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

That's it. Simple but powerful.

Example tree:

Root is 5. It has left child 3 and right child 8. Node 3 has children 1 and 4. Node 8 has only right child 10.

Terminology

Root: Top node (5 in example). No parent.

Leaf: Node with no children (1, 4, 10).

Internal node: Node with at least one child (3, 8).

Height: Length of longest path from root to a leaf. Example tree has height 2 (root → 3 → 1).

Depth: Distance from root to a node. Node 1 has depth 2.

Level: Nodes at same depth. Level 0 is root, level 1 is {3, 8}, level 2 is {1, 4, 10}.

Types of Binary Trees

Full binary tree: Every node has 0 or 2 children. No node with exactly 1 child.

    A
   / \
  B   C
 / \
D   E

Nodes A, B have 2 children. Nodes D, E, C have 0 children. Full.

Complete binary tree: All levels fully filled except possibly last, which fills left to right.

    A
   / \
  B   C
 / \  /
D  E F

Levels 0, 1 full. Level 2 fills left to right (D, E, F). Complete.

Perfect binary tree: All internal nodes have 2 children. All leaves at same level.

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

Perfect. Every level is full. Nodes: 2^(h+1) - 1 where h is height.

Balanced binary tree: Height difference between left and right subtrees of any node ≤ 1.

    A
   / \
  B   C
 /
D

Node A: left subtree height 1, right subtree height 0. Difference is 1. Balanced.

Not balanced:

    A
   /
  B
 /
C

Node A: left subtree height 2, right subtree height 0. Difference is 2. Not balanced.

Why Binary Trees?

Search efficiency: Binary Search Trees (BST) allow O(log n) search on average. Better than arrays for frequent insertions/deletions.

Hierarchical data: File systems, organization charts, expression trees.

Heap: Priority queues use binary heaps (a type of binary tree).

Balanced trees: AVL, Red-Black trees guarantee O(log n) operations.

Array Representation

For complete binary trees, you can use an array instead of pointers.

Tree:
    A
   / \
  B   C
 / \  /
D  E F

Array: [A, B, C, D, E, F]
Indices: 0  1  2  3  4  5

For node at index i:

Left child at 2i + 1
Right child at 2i + 2
Parent at (i - 1) // 2

Example: Node B is at index 1. Left child D at 2(1)+1=3, right child E at 2(1)+2=4. Parent A at (1-1)//2=0.

Great for heaps. Saves memory (no pointers), cache-friendly. But only works well for complete trees (wastes space for sparse trees).

Creating a Binary Tree

# Build tree:
#     1
#    / \
#   2   3
#  /
# 4

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)

Manual construction. For larger trees, you'd use traversal algorithms or read from input.

Tree Size and Height

Size: Total number of nodes.

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

Recursive. Size of tree = 1 (current node) + size of left subtree + size of right subtree.

O(n). Visit every node once.

Height: Longest path from root to leaf.

def height(node):
    if node is None:
        return -1  # Or 0, depending on definition
    return 1 + max(height(node.left), height(node.right))

Height of tree = 1 + max of left and right subtree heights.

O(n). Visit every node once.

Binary Tree vs N-ary Tree

Binary tree: Each node has at most 2 children.

N-ary tree: Each node can have any number of children.

Binary trees are simpler, more studied, easier to analyze. N-ary trees are more flexible.

For example, file systems use n-ary trees (folders can have many children). But for searching, binary trees (BST) are often better.

Example: Expression Tree

Arithmetic expressions as trees.

Expression: (3 + 4) * 2

Tree:

Internal nodes are operators. Leaves are operands.

Evaluate recursively:

def evaluate(node):
    if node is None:
        return 0
    
    # Leaf node (operand)
    if node.left is None and node.right is None:
        return node.value
    
    # Internal node (operator)
    left_val = evaluate(node.left)
    right_val = evaluate(node.right)
    
    if node.value == '+':
        return left_val + right_val
    elif node.value == '*':
        return left_val * right_val
    # ... other operators

Postorder traversal: left, right, root. Process children before parent.

The Foundation

Binary trees are building blocks. They're:

Simple (each node has at most 2 children)
Powerful (enable O(log n) operations)
Versatile (expression trees, heaps, BSTs, decision trees)

Understanding binary trees means understanding:

How to think hierarchically
Recursive algorithms (most tree operations are recursive)
Balance and efficiency (balanced trees vs degenerate trees)

Master binary trees, and you'll handle more complex structures (AVL, Red-Black, B-trees) with ease.