Linked Lists and Trees in Java

Both structures are made of references. Every bug in this area is the same bug: you overwrote a reference before you were done with what it pointed at.

Reversal: the order of three lines

public class Reverse {
    static class Node {
        int val; Node next;
        Node(int v) { val = v; }
    }

    static Node build(int... vals) {
        Node head = null, tail = null;
        for (int v : vals) {
            Node n = new Node(v);
            if (head == null) { head = tail = n; } else { tail.next = n; tail = n; }
        }
        return head;
    }

    static String show(Node head) {
        StringBuilder sb = new StringBuilder();
        for (Node n = head; n != null; n = n.next) sb.append(n.val).append(" -> ");
        return sb.append("null").toString();
    }

    static Node reverse(Node head) {
        Node prev = null, curr = head;
        while (curr != null) {
            Node next = curr.next;   // 1. SAVE before overwriting — everything hinges here
            curr.next = prev;        // 2. flip
            prev = curr;             // 3. advance
            curr = next;
        }
        return prev;                 // curr is null; prev is the new head
    }

    public static void main(String[] args) {
        System.out.println(show(build(1, 2, 3, 4, 5)));
        System.out.println(show(reverse(build(1, 2, 3, 4, 5))));
        System.out.println(show(reverse(build(1))));
        System.out.println(show(reverse(null)));
    }
}

$ java Reverse.java
1 -> 2 -> 3 -> 4 -> 5 -> null
5 -> 4 -> 3 -> 2 -> 1 -> null
1 -> null
null

Drop line 1 and curr.next = prev destroys the only reference to the rest of the list. The remaining nodes become unreachable and the loop terminates one step later with four nodes lost — in Java they are quietly garbage collected rather than crashing, which makes the bug harder to spot than a leak would be.

Returning prev rather than curr is the second trap: the loop exits when curr is null, so curr is never the new head.

Dummy head: deleting the special cases

public class DummyHead {
    static class Node { int val; Node next; Node(int v) { val = v; } }

    static Node withoutDummy(Node head, int target) {
        while (head != null && head.val == target) head = head.next;   // special case
        Node curr = head;
        while (curr != null && curr.next != null) {
            if (curr.next.val == target) curr.next = curr.next.next;
            else curr = curr.next;
        }
        return head;
    }

    static Node withDummy(Node head, int target) {
        Node dummy = new Node(0);
        dummy.next = head;
        Node curr = dummy;
        while (curr.next != null) {
            if (curr.next.val == target) curr.next = curr.next.next;
            else curr = curr.next;
        }
        return dummy.next;                    // no special case at all
    }

    static Node build(int... v) {
        Node h = null, t = null;
        for (int x : v) { Node n = new Node(x); if (h == null) h = t = n; else { t.next = n; t = n; } }
        return h;
    }
    static String show(Node h) {
        StringBuilder sb = new StringBuilder();
        for (Node n = h; n != null; n = n.next) sb.append(n.val).append(" ");
        return sb.length() == 0 ? "(empty)" : sb.toString().trim();
    }

    public static void main(String[] args) {
        System.out.println(show(withDummy(build(1, 2, 6, 3, 4, 5, 6), 6)));
        System.out.println(show(withDummy(build(7, 7, 7), 7)));
        System.out.println(show(withDummy(null, 1)));
        System.out.println(show(withDummy(build(1, 2, 3), 9)));
    }
}

$ java DummyHead.java
1 2 3 4 5
(empty)
(empty)
1 2 3

withDummy is shorter and has no head-specific branch. One extra Node allocation buys the deletion of the case that breaks most first attempts: deleting the head itself.

Use the same idiom whenever you build a list: dummy holds the front while tail walks forward, and you return dummy.next.

Merging two sorted lists

public class Merge {
    static class Node { int val; Node next; Node(int v) { val = v; } }

    static Node merge(Node a, Node b) {
        Node dummy = new Node(0), tail = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }   // <= keeps it stable
            else                { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = (a != null) ? a : b;    // attach the remainder — do not loop over it
        return dummy.next;
    }

    static Node build(int... v) {
        Node h = null, t = null;
        for (int x : v) { Node n = new Node(x); if (h == null) h = t = n; else { t.next = n; t = n; } }
        return h;
    }
    static String show(Node h) {
        StringBuilder sb = new StringBuilder();
        for (Node n = h; n != null; n = n.next) sb.append(n.val).append(" ");
        return sb.length() == 0 ? "(empty)" : sb.toString().trim();
    }

    public static void main(String[] args) {
        System.out.println(show(merge(build(1, 3, 5), build(2, 4, 6))));
        System.out.println(show(merge(build(1, 2, 3), null)));
        System.out.println(show(merge(null, null)));
    }
}

$ java Merge.java
1 2 3 4 5 6
1 2 3
(empty)

tail.next = (a != null) ? a : b attaches the whole remaining chain in O(1) — the rest is already linked. Copying it node by node is the common inefficiency and adds nothing.

Trees: three traversals, one shape

import java.util.*;

public class Traversals {
    static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int v) { val = v; }
        TreeNode(int v, TreeNode l, TreeNode r) { val = v; left = l; right = r; }
    }

    static TreeNode sample() {
        return new TreeNode(1,
            new TreeNode(2, new TreeNode(4), new TreeNode(5)),
            new TreeNode(3, null, new TreeNode(6)));
    }

    static void inorder(TreeNode n, List<Integer> out) {
        if (n == null) return;
        inorder(n.left, out);  out.add(n.val);  inorder(n.right, out);
    }
    static void preorder(TreeNode n, List<Integer> out) {
        if (n == null) return;
        out.add(n.val);  preorder(n.left, out);  preorder(n.right, out);
    }
    static void postorder(TreeNode n, List<Integer> out) {
        if (n == null) return;
        postorder(n.left, out);  postorder(n.right, out);  out.add(n.val);
    }

    public static void main(String[] args) {
        List<Integer> a = new ArrayList<>(), b = new ArrayList<>(), c = new ArrayList<>();
        inorder(sample(), a); preorder(sample(), b); postorder(sample(), c);
        System.out.println("inorder    " + a);
        System.out.println("preorder   " + b);
        System.out.println("postorder  " + c);
    }
}

$ java Traversals.java
inorder    [4, 2, 5, 1, 3, 6]
preorder   [1, 2, 4, 5, 3, 6]
postorder  [4, 5, 6, 2, 3, 1]

The three differ only in where out.add sits. What each is for:

• Inorder — on a BST, produces sorted order. That is the whole reason BST validation uses it.
• Preorder — root first; serialisation and copying.
• Postorder — children before parent; deletion, and any computation depending on subtrees.

Level order: the size snapshot

import java.util.*;

public class LevelOrder {
    static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int v) { val = v; }
        TreeNode(int v, TreeNode l, TreeNode r) { val = v; left = l; right = r; }
    }

    static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> out = new ArrayList<>();
        if (root == null) return out;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();          // snapshot BEFORE adding children
            List<Integer> level = new ArrayList<>(levelSize);
            for (int i = 0; i < levelSize; i++) {
                TreeNode n = queue.poll();
                level.add(n.val);
                if (n.left != null) queue.offer(n.left);
                if (n.right != null) queue.offer(n.right);
            }
            out.add(level);
        }
        return out;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1,
            new TreeNode(2, new TreeNode(4), new TreeNode(5)),
            new TreeNode(3, null, new TreeNode(6)));
        System.out.println(levelOrder(root));
        System.out.println(levelOrder(null));
    }
}

$ java LevelOrder.java
[[1], [2, 3], [4, 5, 6]]
[]

int levelSize = queue.size() taken before the inner loop is the entire trick. Children pushed during the loop belong to the next level and are correctly excluded by the snapshot. Without it, the loop drains everything and you get one flat list.

ArrayDeque is the queue here — offer/poll at opposite ends. Using LinkedList also works and allocates a node per element.

Recursion depth: where Java breaks

public class Depth {
    static class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } }

    static int depthRecursive(TreeNode n) {
        if (n == null) return 0;
        return 1 + Math.max(depthRecursive(n.left), depthRecursive(n.right));
    }

    static int depthIterative(TreeNode root) {
        if (root == null) return 0;
        java.util.Deque<TreeNode> stack = new java.util.ArrayDeque<>();
        java.util.Deque<Integer> depths = new java.util.ArrayDeque<>();
        stack.push(root); depths.push(1);
        int best = 0;
        while (!stack.isEmpty()) {
            TreeNode n = stack.pop(); int d = depths.pop();
            best = Math.max(best, d);
            if (n.left  != null) { stack.push(n.left);  depths.push(d + 1); }
            if (n.right != null) { stack.push(n.right); depths.push(d + 1); }
        }
        return best;
    }

    public static void main(String[] args) {
        TreeNode chain = new TreeNode(0), curr = chain;
        for (int i = 1; i < 100_000; i++) { curr.right = new TreeNode(i); curr = curr.right; }

        System.out.println("iterative: " + depthIterative(chain));
        try {
            System.out.println("recursive: " + depthRecursive(chain));
        } catch (StackOverflowError e) {
            System.out.println("recursive: StackOverflowError");
        }
    }
}

$ java Depth.java
iterative: 100000
recursive: StackOverflowError

A 100,000-node chain is 100,000 frames deep. A 100,000-node balanced tree is 17 deep and recursion is fine. The distinction is the answer:

“Recursion is cleaner and I would write it first. It overflows at roughly ten to twenty thousand frames on the default stack, so if the input can be a degenerate chain — a linked list shaped like a tree — I would use the explicit-stack version, or note that the constraint n <= 5000 makes recursion safe.”

Catching StackOverflowError as this demo does is fine for illustration and wrong in production — an Error signals the JVM is in a state you should not continue from.

Validating a BST — the trap

public class ValidateBST {
    static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int v) { val = v; }
        TreeNode(int v, TreeNode l, TreeNode r) { val = v; left = l; right = r; }
    }

    static boolean wrong(TreeNode n) {
        if (n == null) return true;
        if (n.left  != null && n.left.val  >= n.val) return false;
        if (n.right != null && n.right.val <= n.val) return false;
        return wrong(n.left) && wrong(n.right);      // only checks direct children
    }

    static boolean correct(TreeNode n, Integer lo, Integer hi) {
        if (n == null) return true;
        if (lo != null && n.val <= lo) return false;
        if (hi != null && n.val >= hi) return false;
        return correct(n.left, lo, n.val) && correct(n.right, n.val, hi);
    }

    public static void main(String[] args) {
        // 5 / (1, 4 / (3, 6))  — 3 is in the right subtree of 5 but smaller than 5
        TreeNode tricky = new TreeNode(5,
            new TreeNode(1),
            new TreeNode(4, new TreeNode(3), new TreeNode(6)));
        System.out.println("child-only check: " + wrong(tricky));
        System.out.println("range check:      " + correct(tricky, null, null));

        TreeNode good = new TreeNode(2, new TreeNode(1), new TreeNode(3));
        System.out.println("valid BST:        " + correct(good, null, null));
    }
}

$ java ValidateBST.java
child-only check: true
range check:      false
valid BST:        true

The child-only check passes a tree that is not a BST. Every node must be inside a range inherited from its ancestors, not merely ordered against its parent.

Integer rather than int for the bounds avoids the classic Integer.MIN_VALUE sentinel bug — a tree containing Integer.MIN_VALUE would be rejected. Using long bounds is the other common fix; Integer with null is clearer.

Recognising it

SIGNAL                                       APPROACH
reverse / reorder a list                     prev-curr-next, save before overwriting
delete nodes, insert at head                 dummy head, return dummy.next
merge sorted lists                           dummy head + tail, attach remainder in O(1)
find the middle, detect a cycle              fast/slow pointers
"sorted order" from a BST                    inorder traversal
serialise / copy a tree                      preorder
compute from subtrees upward                 postorder
"level by level", "shortest path in a tree"  BFS with a queue.size() snapshot
validate a BST                               recursion carrying (lo, hi) bounds
input can be a degenerate chain              iterative with an explicit ArrayDeque

Practice

1 -> null      (four nodes silently lost)

withDummy(7 7 7, target 7) -> (empty)

StackOverflowError

child-only check: true      range check: false

Next: graphs — BFS and DFS on adjacency lists, cycle detection with three colours, and topological sort.