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

Term	Definition
Root	Topmost node (no parent)
Leaf	Node with no children
Height	Longest path from node to leaf
Depth	Distance from root to node
Degree	Number of children (0, 1, or 2)

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

Aspect	DFS	BFS
Data Structure	Stack (or recursion)	Queue
Space Complexity	O(h) height	O(w) max width
Use Case	Path finding, tree height	Level-order, shortest path
Iterative?	Yes (with explicit stack)	Yes (with queue)

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