Binary Trees — Traversals & Operations

Introduction

So far, all the data structures we have looked at — Arrays, Stacks, Queues, and Linked Lists — have been linear. You start at one end and go to the other.

But the real world is rarely linear. A company’s organisational chart, the folder structure on your computer, and the DOM of a web page are all hierarchical. To represent this in programming, we use Trees.

The most fundamental tree in computer science is the Binary Tree — a tree where every node has at most two children.

Anatomy of a Binary Tree

Just like a Linked List has a Node with a next pointer, a Binary Tree has a TreeNode with left and right pointers.

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

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

Terminology

• Root: The topmost node (1). The entry point to the tree.
• Parent/Child: Node 2 is the parent of 4 and 5.
• Siblings: Nodes 4 and 5 share the same parent, so they are siblings.
• Leaf: A node with NO children (4, 5, 7).
• Depth: The number of edges from the root to a node (Node 5 has depth 2).
• Height: The max depth of the tree (This tree has height 2).

Tree Traversals

In an array, there is an obvious way to visit every element (index 0 to n-1). In a tree, there are four main ways to visit every node. Which one you choose depends entirely on the problem you are solving.

Let’s use the tree above as our example.

1. In-order Traversal (Left, Root, Right)

You visit the left branch entirely, then print the current node, then visit the right branch entirely. (Used primarily in Binary Search Trees to get elements in sorted order).

Output: 4, 2, 5, 1, 3, 7

public void inorderTraversal(TreeNode root) {
    if (root == null) return;
    inorderTraversal(root.left);       // go left
    System.out.print(root.val + " ");  // visit root
    inorderTraversal(root.right);      // go right
}

2. Pre-order Traversal (Root, Left, Right)

You print the current node before visiting its children. (Used for copying a tree or evaluating mathematical expression trees).

Output: 1, 2, 4, 5, 3, 7

public void preorderTraversal(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");  // visit root First
    preorderTraversal(root.left);      // go left
    preorderTraversal(root.right);     // go right
}

3. Post-order Traversal (Left, Right, Root)

You visit both children entirely before printing the current node. (Used for deleting a tree from the bottom up).

Output: 4, 5, 2, 7, 3, 1

public void postorderTraversal(TreeNode root) {
    if (root == null) return;
    postorderTraversal(root.left);     // go left
    postorderTraversal(root.right);    // go right
    System.out.print(root.val + " ");  // visit root Last
}

4. Level-order Traversal (Breadth-First Search)

You visit the nodes layer by layer, top to bottom, left to right. (Used for finding the shortest path in unweighted graphs).

Output: 1, 2, 3, 4, 5, 7

Unlike the first three (which use recursion/Stacks to go deep), BFS uses a Queue.

import java.util.LinkedList;
import java.util.Queue;

public void levelOrderTraversal(TreeNode root) {
    if (root == null) return;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root); // Start with the root
    
    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();
        System.out.print(current.val + " ");
        
        // Add children to the back of the line
        if (current.left != null) queue.offer(current.left);
        if (current.right != null) queue.offer(current.right);
    }
}

Basic Operations & Recursion Patterns

Because trees are inherently recursive data structures, almost all tree algorithms are written using recursion. Here are two classic examples you must know:

1. Finding the Max Depth (Height)

To find how tall a tree is, you ask a simple recursive question: “How deep is my left side, and how deep is my right side? Take the biggest one, and add 1 for myself.”

public int maxDepth(TreeNode root) {
    if (root == null) return 0; // base case: empty tree has depth 0
    
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    
    return Math.max(leftDepth, rightDepth) + 1;
}

2. Inverting a Binary Tree

Famous for being the problem that tripped up the creator of Homebrew in a Google interview. It is surprisingly simple: swap the left and right pointers of the current node, then recurse down.

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    
    // Swap the left and right children
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    
    // Recurse down
    invertTree(root.left);
    invertTree(root.right);
    
    return root;
}

When to Use / When NOT to Use

A plain Binary Tree is mainly a foundational concept. In practice, you almost never use a “plain” Binary Tree where data is inserted randomly.

Instead, you use constrained versions of binary trees that enforce rules:

• Binary Search Trees enforce sorting for $O(\log n)$ search.
• Heaps enforce max/min values at the root for priority queues.

Practice Problems

1. Binary Tree Inorder Traversal – LeetCode #94 — Write it recursively, then try the challenge of doing it iteratively with a Stack.
2. Maximum Depth of Binary Tree – LeetCode #104 — Classic recursive problem.
3. Invert Binary Tree – LeetCode #226 — The legendary interview question.
4. Same Tree – LeetCode #100 — Use recursion to traverse two trees simultaneously and compare them.

What’s Next?

A standard Binary Tree lets us store hierarchical data, but if we want to search that data efficiently, we need rules. Next up, we combine the structure of a tree with the logic of Binary Search to create the Binary Search Tree (BST).