The Tree ADT: Traversals and Binary Search Trees

Everything so far has been linear: each element has a previous and a next, and finding something means, in the worst case, walking all of it.

A tree breaks that linearity. Each node can have several children, and that unlocks something powerful: discarding half the data at every step. Searching a million elements stops costing a million comparisons and starts costing twenty.

On top of that, plenty of real things are trees: the file system, a page’s DOM, a company org chart, Java’s own class hierarchy, a game’s decision space.

1. Vocabulary

The class that models it is the sibling of the Node from the The List ADT: Static, Dynamic, and Linked lesson, with one more reference:

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        this.value = value;
    }
}

public class BinaryTree {
    private TreeNode root;   // same as 'head', just named root here
}

And because each node has two children that are themselves complete trees, everything about trees is solved with recursion. This is the data structure where recursion stops being an academic exercise and becomes the natural tool.

2. The three depth-first traversals

Walking a list has exactly one possible order. A tree has several, and each is good for something different.

All three differ only in where the root is processed relative to its subtrees:

The code is nearly identical in all three cases. The only thing that moves is one line:

public void preOrder(TreeNode node) {
    if (node == null) return;               // base case: always first
    System.out.print(node.value + " ");     // ← the root, BEFORE
    preOrder(node.left);
    preOrder(node.right);
}

public void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    System.out.print(node.value + " ");     // ← the root, IN BETWEEN
    inOrder(node.right);
}

public void postOrder(TreeNode node) {
    if (node == null) return;
    postOrder(node.left);
    postOrder(node.right);
    System.out.print(node.value + " ");     // ← the root, AFTER
}

The if (node == null) return; is the base case, and it is not a detail: without it the recursion never ends and you get a StackOverflowError. Which, as you saw in the The Stack and Queue ADTs: Linear Structures lesson, is literally the JVM call stack overflowing.

In-order over a BST yields sorted data. That property, which looks like a magic trick, is why a TreeMap can be iterated in key order without sorting anything: the order is already in the shape of the tree.

3. Level-order traversal (BFS), with a queue

The three traversals above dive to the bottom before moving sideways. Sometimes you want the opposite: visiting the tree level by level.

Recursion is no help here. What helps is a queue, exactly the one from the The Stack and Queue ADTs: Linear Structures lesson:

public void levelOrder() {
    if (root == null) return;

    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();
        System.out.print(current.value + " ");

        if (current.left  != null) queue.offer(current.left);
        if (current.right != null) queue.offer(current.right);
    }
}
// Output: 50 30 70 20 40 60 80

Notice the mechanism: I enqueue the children and only process them once I have finished the whole current level. That first-in-first-out behavior is exactly what produces level order.

Swap the queue for a stack and you get a depth-first traversal without recursion. Changing the structure changes the algorithm without touching the rest of the code. Same idea you will use for graphs, in the next lesson.

4. The Binary Search Tree

So far trees just held data. A BST adds one rule that changes everything:

For every node: every value in the left subtree is smaller, and every value in the right subtree is larger.

With that rule, searching stops being traversal and becomes decision:

public boolean search(int value) {
    return search(root, value);
}

private boolean search(TreeNode node, int value) {
    if (node == null) return false;               // hit the void: not there
    if (value == node.value) return true;         // found it
    return value < node.value
        ? search(node.left, value)                // smaller: go left
        : search(node.right, value);              // larger: go right
}

Insertion uses exactly the same logic: descend until you find an empty spot and hang the new node there.

public void insert(int value) {
    root = insert(root, value);
}

private TreeNode insert(TreeNode node, int value) {
    if (node == null) return new TreeNode(value);   // this is the spot

    if (value < node.value) {
        node.left = insert(node.left, value);
    } else if (value > node.value) {
        node.right = insert(node.right, value);
    }
    // if equal, do nothing: a BST holds no duplicates
    return node;
}

The node.left = insert(node.left, value) pattern — reassigning the recursion’s result — is the idiomatic way to modify trees in Java. It saves you from carrying a reference to the parent.

5. The Achilles heel: imbalance

Everything above assumes the tree is shaped like a tree. But that is not guaranteed:

This is why you will not implement a BST in production. TreeMap and TreeSet are red-black trees: they rearrange themselves with rotations on every insertion and guarantee O(log n) regardless of the order the data arrives in.

What you take away is understanding why they are O(log n) and what would happen if they did not rebalance.

6. Common mistakes

7. Guided hands-on exercise

Challenge: complete the BST

Implement on BinarySearchTree:

1. insert(int value), no duplicates.
2. search(int value) returning a boolean.
3. height() of the tree.
4. countNodes() and countLeaves().
5. isValidBST() verifying the property holds across the entire tree.
6. The three depth-first traversals plus level-order.

Point 5 is harder than it looks. Think it through before peeking.

import java.util.ArrayDeque;
import java.util.Queue;

public class BinarySearchTree {

    private static class TreeNode {
        int value;
        TreeNode left, right;
        TreeNode(int value) { this.value = value; }
    }

    private TreeNode root;

    // ── 1. Insertion ────────────────────────────────────────────
    public void insert(int value) {
        root = insert(root, value);
    }

    private TreeNode insert(TreeNode node, int value) {
        if (node == null) return new TreeNode(value);
        if (value < node.value)      node.left  = insert(node.left, value);
        else if (value > node.value) node.right = insert(node.right, value);
        // equal → ignored, no duplicates allowed
        return node;   // returning the node is what makes the reassignment work
    }

    // ── 2. Search ───────────────────────────────────────────────
    public boolean search(int value) {
        return search(root, value);
    }

    private boolean search(TreeNode node, int value) {
        if (node == null) return false;
        if (value == node.value) return true;
        return value < node.value ? search(node.left, value)
                                  : search(node.right, value);
    }

    // ── 3. Height ───────────────────────────────────────────────
    public int height() {
        return height(root);
    }

    private int height(TreeNode node) {
        if (node == null) return -1;   // -1 so that a leaf has height 0
        return 1 + Math.max(height(node.left), height(node.right));
    }

    // ── 4. Counts ───────────────────────────────────────────────
    public int countNodes() { return countNodes(root); }

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

    public int countLeaves() { return countLeaves(root); }

    private int countLeaves(TreeNode node) {
        if (node == null) return 0;
        if (node.left == null && node.right == null) return 1;
        return countLeaves(node.left) + countLeaves(node.right);
    }

    // ── 5. BST validation ───────────────────────────────────────
    public boolean isValidBST() {
        return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    // The key: every node inherits an allowed RANGE, not just a comparison
    // with its immediate parent. Going left tightens the maximum to the
    // parent's value; going right tightens the minimum.
    private boolean isValid(TreeNode node, long min, long max) {
        if (node == null) return true;
        if (node.value <= min || node.value >= max) return false;
        return isValid(node.left,  min, node.value)
            && isValid(node.right, node.value, max);
    }

    // ── 6. Traversals ───────────────────────────────────────────
    public void preOrder()  { preOrder(root);  System.out.println(); }
    public void inOrder()   { inOrder(root);   System.out.println(); }
    public void postOrder() { postOrder(root); System.out.println(); }

    private void preOrder(TreeNode n) {
        if (n == null) return;
        System.out.print(n.value + " ");
        preOrder(n.left);
        preOrder(n.right);
    }

    private void inOrder(TreeNode n) {
        if (n == null) return;
        inOrder(n.left);
        System.out.print(n.value + " ");
        inOrder(n.right);
    }

    private void postOrder(TreeNode n) {
        if (n == null) return;
        postOrder(n.left);
        postOrder(n.right);
        System.out.print(n.value + " ");
    }

    public void levelOrder() {
        if (root == null) { System.out.println("(empty)"); return; }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            System.out.print(current.value + " ");
            if (current.left  != null) queue.offer(current.left);
            if (current.right != null) queue.offer(current.right);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        for (int v : new int[]{50, 30, 70, 20, 40, 60, 80}) {
            tree.insert(v);
        }

        System.out.print("Pre-order  : "); tree.preOrder();    // 50 30 20 40 70 60 80
        System.out.print("In-order   : "); tree.inOrder();     // 20 30 40 50 60 70 80
        System.out.print("Post-order : "); tree.postOrder();   // 20 40 30 60 80 70 50
        System.out.print("Level-order: "); tree.levelOrder();  // 50 30 70 20 40 60 80

        System.out.println("\nHeight       : " + tree.height());        // 2
        System.out.println("Nodes        : " + tree.countNodes());      // 7
        System.out.println("Leaves       : " + tree.countLeaves());     // 4
        System.out.println("search(40)   : " + tree.search(40));        // true
        System.out.println("search(45)   : " + tree.search(45));        // false
        System.out.println("isValidBST() : " + tree.isValidBST());      // true

        // Imbalance demonstration
        BinarySearchTree degenerate = new BinarySearchTree();
        for (int v : new int[]{10, 20, 30, 40, 50, 60, 70}) {
            degenerate.insert(v);
        }
        System.out.println("\nSame 7 values, inserted in sorted order:");
        System.out.println("Height: " + degenerate.height() + "  ← was 2, now 6");
    }
}

// WRONG: only looks at the immediate parent
if (node.left != null && node.left.value >= node.value) return false;

      50
     /  \
   30    70
  /  \
20    60      ← 60 is greater than 50 and sits in 50's LEFT subtree

Key takeaways

• A tree breaks linearity and lets you discard half the data at every step.
• Everything about trees is solved with recursion, and every recursive method starts with its base case.
• The three DFS traversals differ by exactly one line: where the root is processed.
• In-order over a BST returns sorted data. That is why TreeMap iterates in order without sorting anything.
• Level-order traversal (BFS) needs a queue, not recursion.
• The BST property — smaller left, larger right, across the whole tree — is what turns a search into a decision.
• Inserting already-sorted data degenerates a BST into a list and drops it from O(log n) to O(n).
• In production use TreeMap/TreeSet: red-black trees that rebalance themselves.