Binary Trees

A binary tree is a hierarchical data structure where each node has at most two children, referred to as left and right.

Node Structure

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Key Terminology

Tree Types

• Full Binary Tree: Every node has 0 or 2 children
• Complete Binary Tree: All levels filled except possibly last, filled left to right
• Balanced Binary Tree: Height difference between left and right subtrees ≤ 1

Visual Example

        1          ← Root (depth=0, height=3)
       / \
      2   3        ← depth=1
     / \\   \
    4   5   6      ← depth=2
   / \\      \
  7   8      9     ← Leaves (depth=3)

Building a Binary Tree

// Manual construction
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

Computing Height Recursively

public int height(TreeNode root) {
    if (root == null) return -1;  // or 0 for node count
    return 1 + Math.max(height(root.left), height(root.right));
}

Counting Nodes

public int countNodes(TreeNode root) {
    if (root == null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
}

Key Insight: Recursive Thinking

Every binary tree problem follows the same pattern:

1. Base case: null node → return default value
2. Recursive case: solve for left subtree, solve for right subtree
3. Combine: use current node's value with left/right results

This "trust the recursion" approach is the foundation of all tree problems.

Depth-First Search (DFS)

Explores as deep as possible before backtracking. Three variants:

// 1. Pre-order: Root → Left → Right
public void preorder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");  // Visit root first
    preorder(root.left);
    preorder(root.right);
}

// 2. In-order: Left → Root → Right
public void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.val + " ");  // Visit root between
    inorder(root.right);
}

// 3. Post-order: Left → Right → Root
public void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.print(root.val + " ");  // Visit root last
}

Breadth-First Search (BFS)

Explores level by level using a queue:

public void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        System.out.println();  // New level
    }
}

Comparison

When to Use What

• DFS: Problems involving paths, subtrees, or exploring all possibilities
• BFS: Problems involving level-by-level processing, minimum depth, or shortest path