Binary Trees

A tree with n nodes always has exactly n - 1 edges.

Definition

A binary tree is a tree in which every node has at most two children, conventionally labelled left and right.

Key properties

• Maximum nodes at depth d: 2d
• Maximum total nodes with height h: 2h+1 - 1
• Minimum height for n nodes: floor(log2(n))
• NULL pointers in tree with n nodes: n + 1
• Full binary tree with n internal nodes has n + 1 leaves

Node structure

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

The recursive structure of TreeNode mirrors the recursive nature of every binary tree algorithm.

        1
       / \
      2   3
     / \
    4   5

        1
       / \
      2   3
     / \ /
    4  5 6

Left → Root → Right

Visit the left subtree, then the current node, then the right subtree. For a BST, inorder produces sorted output.

def inorder(root):
    if root is None:
        return
    inorder(root.left)
    visit(root.val)
    inorder(root.right)

Applications

• Retrieve BST elements in sorted order
• Expression tree evaluation (infix notation)
• Validate whether a binary tree is a BST

Example

Time: O(n). Space: O(h) for the recursion stack.

def preorder(root):
    if root is None:
        return
    visit(root.val)
    preorder(root.left)
    preorder(root.right)

• First element is always the root
• Used to serialise / copy a tree
• Preorder sequence + structure info reconstructs the tree

def postorder(root):
    if root is None:
        return
    postorder(root.left)
    postorder(root.right)
    visit(root.val)

• Last element is always the root
• Delete a tree (children before parent)
• Postfix expression evaluation
• Compute directory sizes (children first)

Iterative inorder

def inorder_iterative(root):
    stack, current = [], root
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        visit(current.val)
        current = current.right

Iterative preorder

def preorder_iterative(root):
    if not root:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        visit(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

Breadth-first, level by level

Visit all nodes at depth d before depth d + 1. Uses a queue instead of a stack.

from collections import deque

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level_size = len(queue)
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

Example

Applications

• Finding minimum depth of a tree
• Zigzag (spiral) traversal
• Connecting next pointers at same level
• Serialisation with NULL markers

Time: O(n). Space: O(w) where w is max width.

def morris_inorder(root):
    current = root
    while current:
        if current.left is None:
            visit(current.val)
            current = current.right
        else:
            # Find inorder predecessor
            pred = current.left
            while (pred.right and
                   pred.right != current):
                pred = pred.right

            if pred.right is None:
                # Create thread
                pred.right = current
                current = current.left
            else:
                # Remove thread, visit
                pred.right = None
                visit(current.val)
                current = current.right

How it works

The tree is restored to its original shape. Each edge is traversed at most twice.

Which pairs uniquely determine a tree?

Algorithm: inorder + preorder

def build_tree(preorder, inorder):
    if not inorder:
        return None
    root_val = preorder.pop(0)
    root = TreeNode(root_val)
    mid = inorder.index(root_val)
    root.left  = build_tree(
        preorder, inorder[:mid])
    root.right = build_tree(
        preorder, inorder[mid+1:])
    return root

Optimisation

Use a hash map for O(1) index lookup and a pointer into preorder instead of pop(0). Reduces time from O(n2) to O(n).

Definition

The LCA of two nodes p and q is the deepest node that is an ancestor of both.

def lca(root, p, q):
    if (root is None or
        root == p or root == q):
        return root
    left  = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right:
        return root       # split point
    return left or right  # same side

Complexity

Time: O(n). Space: O(h) recursion stack.

How it works

Definition

The diameter is the longest path between any two nodes, measured in edges. The path may or may not pass through the root.

def diameter(root):
    max_d = 0

    def height(node):
        nonlocal max_d
        if node is None:
            return -1
        lh = height(node.left)
        rh = height(node.right)
        max_d = max(max_d, lh + rh + 2)
        return max(lh, rh) + 1

    height(root)
    return max_d

Key insight

At each node, the longest path through that node is left_height + right_height + 2. The diameter is the maximum across all nodes.

Preorder with NULL markers

def serialise(root):
    if root is None:
        return "# "
    return (str(root.val) + " "
            + serialise(root.left)
            + serialise(root.right))

def deserialise(data):
    tokens = iter(data.split())
    def build():
        val = next(tokens)
        if val == "#":
            return None
        node = TreeNode(int(val))
        node.left  = build()
        node.right = build()
        return node
    return build()

Example

    1
   / \
  2   3
     / \
    4   5

Serialised: "1 2 # # 3 4 # # 5 # #"

Alternative approaches

The NULL pointer problem

In a binary tree with n nodes, there are n + 1 NULL pointers (wasted space). Threaded binary trees repurpose these NULLs to point to inorder predecessors/successors.

Node structure

class ThreadedNode:
    def __init__(self, val):
        self.val = val
        self.left  = None
        self.right = None
        self.left_thread  = False
        self.right_thread = False

Benefits

• Inorder traversal without stack/recursion — O(1) space
• Inorder successor/predecessor in O(1) amortised
• Morris traversal creates temporary threads on the fly

Definition

A binary tree representing an arithmetic expression. Leaves are operands, internal nodes are operators.

Traversals produce different notations

Building from postfix

def build_expr_tree(postfix):
    stack = []
    ops = {'+', '-', '*', '/'}
    for token in postfix:
        node = TreeNode(token)
        if token in ops:
            node.right = stack.pop()
            node.left  = stack.pop()
        stack.append(node)
    return stack[0]

Directory trees

File systems are naturally tree-structured. Each directory is an internal node; files are leaves.

/
├── home/
│   ├── alice/
│   │   ├── docs/
│   │   │   └── report.pdf
│   │   └── .bashrc
│   └── bob/
│       └── code/
│           └── main.py
├── etc/
│   └── config.yaml
└── var/
    └── log/
        └── syslog

Tree operations in file systems

document
└── html
    ├── head
    │   ├── title
    │   └── link
    └── body
        ├── div#header
        │   └── h1
        └── div#content
            ├── p
            └── ul
                ├── li
                └── li

• CSS selectors traverse the tree
• getElementById() is a tree search
• DOM diffing (React, Vue) compares two trees

          Is temp > 30?
         /             \
       Yes              No
    Is humid?       Is windy?
     /    \          /     \
   Yes    No      Yes      No
  Stay  Beach    Stay     Park
 inside          inside

• Each root-to-leaf path is a decision rule
• Training: split data to maximise information gain
• Random forests: ensemble of many decision trees
• Used in medicine, finance, recommendations

Key takeaways

• A binary tree is defined by the constraint of at most two children per node
• Tree shape matters: balanced gives O(log n), degenerate gives O(n)
• Master all three DFS traversals in both recursive and iterative forms
• Level-order (BFS) solves level-aware problems naturally
• Morris traversal achieves O(1) space via temporary threads
• LCA and diameter are canonical post-order accumulation problems
• Serialisation converts structure to string and back — essential for distributed systems
• Expression trees connect traversals to notation systems
• Trees are everywhere: file systems, DOM, decision trees, compiler ASTs, database indexes

Recommended reading