codeloopback
Guide contents

Lesson 93 of 164

Binary Trees and BSTs in Java

A tree is a set of nodes connected by edges, with one node at the top (the root) and no cycles. In a binary tree, each node has at most two children, called left and right.

graph TB
    r["6 (root)"] --> a["4"]
    r --> b["9"]
    a --> c["2 (leaf)"]
    a --> d["5 (leaf)"]
    b --> e["8 (leaf)"]
    b --> f["12"]
    f --> g["10 (leaf)"]
Term Meaning In the diagram
root the top node, with no parent 6
leaf a node with no children 2, 5, 8, 10
parent / child nodes directly connected by an edge 9 is the parent of 8 and 12
ancestor a node on the path from the root to a node 6 and 9 are ancestors of 12
depth of a node the number of edges from the root to it depth(12) = 2
height of a tree the number of edges on the longest root-to-leaf path 3 (6 → 9 → 12 → 10)
subtree a node together with all of its descendants the subtree at 9 is {9, 8, 12, 10}

Binary search trees

A binary search tree (BST) is a binary tree with an ordering rule: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger (this course puts equal values on the right). The tree above is a BST.

The ordering means a search only ever goes down one path: at each node, compare and go left or right. The cost of search, insert, and delete is O(h), where h is the tree's height:

Tree shape Height Search / insert / delete
balanced (built from shuffled input) O(log n) O(log n)
degenerate (built from sorted input) O(n) O(n) 
graph TB
    subgraph skewed["inserting 1, 2, 3, 4 in order"]
        s1["1"] --> s2["2"] --> s3["3"] --> s4["4"]
    end

Self-balancing trees (AVL, red-black) keep the height at O(log n) automatically. Java's TreeMap and TreeSet are balanced red-black trees, so they are the ready-made ordered map and set.

The node type

Each node holds two references, left and right, to child nodes. An empty subtree is null, so a TreeNode reference doubles as "a possibly empty tree". This is the same idea as a linked list's next, but with two links. Fields are mutable, so no Box or Option wrapper is needed.

Java
public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(4);
        root.right = new TreeNode(9);
        System.out.println("right child of the root: " + root.right.val);
    }
}
Output
right child of the root: 9

Insert walks down from the root with a reference cur, going left or right until the link it needs is null, then stores the new node there. It returns the root, so that inserting into an empty tree (null) works too.

Search only reads: it walks down the same way and stops at a match or at null.

Java
public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    static TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = new TreeNode(val); break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = new TreeNode(val); break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static boolean contains(TreeNode root, int val) {
        TreeNode cur = root;
        while (cur != null) {
            if (val == cur.val) return true;
            cur = val < cur.val ? cur.left : cur.right;
        }
        return false;
    }

    public static void main(String[] args) {
        TreeNode root = null;
        for (int v : new int[] {6, 4, 9, 2, 5, 8, 12, 10}) {
            root = insert(root, v);
        }
        System.out.println(contains(root, 5) + " " + contains(root, 7));
    }
}
Output
true false

Walkthrough of contains(7): 6 → go right (7 > 6) → 9 → go left (7 < 9) → 8 → go left (7 < 8) → null. Not found after 3 comparisons.

Delete by returning the new subtree

Deleting has three cases:

  1. Leaf: remove it.
  2. One child: replace the node with that child.
  3. Two children: replace the node's value with its in-order successor (the smallest value in its right subtree), then remove the successor from the right subtree. The successor has no left child, so removing it is case 1 or 2.

The cleanest version is recursive: delete(root, val) returns the root of the subtree after the deletion, and the caller stores that result in its left or right field. A removed node is replaced by returning null or a child, and the garbage collector reclaims the unreferenced node.

Java
import java.util.ArrayList;
import java.util.List;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    static TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = new TreeNode(val); break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = new TreeNode(val); break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static TreeNode minNode(TreeNode node) {
        while (node.left != null) node = node.left;
        return node;
    }

    static TreeNode delete(TreeNode root, int val) {
        if (root == null) return null;
        if (val < root.val) {
            root.left = delete(root.left, val);
        } else if (val > root.val) {
            root.right = delete(root.right, val);
        } else {
            if (root.left == null) return root.right;  // leaf, or only a right child
            if (root.right == null) return root.left;  // only a left child
            TreeNode successor = minNode(root.right);
            root.val = successor.val;
            root.right = delete(root.right, successor.val); // remove the successor node
        }
        return root;
    }

    static void inOrder(TreeNode root, List<Integer> out) {
        if (root == null) return;
        inOrder(root.left, out);
        out.add(root.val);
        inOrder(root.right, out);
    }

    public static void main(String[] args) {
        TreeNode root = null;
        for (int v : new int[] {6, 4, 9, 2, 5, 8, 12}) {
            root = insert(root, v);
        }
        root = delete(root, 6); // two children: replaced by its successor, 8
        root = delete(root, 2); // a leaf
        List<Integer> out = new ArrayList<>();
        inOrder(root, out);
        System.out.println(out + ", new root = " + root.val);
    }
}
Output
[4, 5, 8, 9, 12], new root = 8

The successor is removed with a second delete call on the right subtree. That call walks down to the successor, which has no left child, so it takes the "only a right child" or leaf branch. This costs O(h) in total.

Traversals

A traversal visits every node once. The four standard orders:

Order Visit For the example tree Used for
pre-order node, left, right 6 4 2 5 9 8 12 10 copying or serializing a tree
in-order left, node, right 2 4 5 6 8 9 10 12 a BST's values in sorted order
post-order left, right, node 2 5 4 8 10 12 9 6 computing heights and sizes, freeing nodes
level-order level by level, left to right 6 4 9 2 5 8 12 10 distances from the root

The first three are depth-first and are easiest to write recursively. Level-order is breadth-first and uses a queue. ArrayDeque is Java's array-backed double-ended queue. It serves as the queue (add at the back, poll from the front) and as the stack (push and pop at the front). It rejects null, so only real nodes are stored.

Java
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Queue;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    static TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = new TreeNode(val); break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = new TreeNode(val); break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static void preOrder(TreeNode root, List<Integer> out) {
        if (root == null) return;
        out.add(root.val);
        preOrder(root.left, out);
        preOrder(root.right, out);
    }

    static void postOrder(TreeNode root, List<Integer> out) {
        if (root == null) return;
        postOrder(root.left, out);
        postOrder(root.right, out);
        out.add(root.val);
    }

    // In-order without recursion: go left as far as possible, visit, then turn right.
    static List<Integer> inOrder(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            out.add(node.val);
            cur = node.right;
        }
        return out;
    }

    static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (root == null) return levels;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            levels.add(level);
        }
        return levels;
    }

    public static void main(String[] args) {
        TreeNode root = null;
        for (int v : new int[] {6, 4, 9, 2, 5, 8, 12, 10}) {
            root = insert(root, v);
        }
        List<Integer> pre = new ArrayList<>();
        List<Integer> post = new ArrayList<>();
        preOrder(root, pre);
        postOrder(root, post);
        System.out.println("pre   " + pre);
        System.out.println("in    " + inOrder(root));
        System.out.println("post  " + post);
        System.out.println("level " + levelOrder(root));
    }
}
Output
pre   [6, 4, 2, 5, 9, 8, 12, 10]
in    [2, 4, 5, 6, 8, 9, 10, 12]
post  [2, 5, 4, 8, 10, 12, 9, 6]
level [[6], [4, 9], [2, 5, 8, 12], [10]]

A few details in this code:

  • A root of null is handled up front in levelOrder, because ArrayDeque cannot hold null.
  • int size = queue.size() reads the length once, at the start of the level, so children added during the loop belong to the next level.
  • The iterative in-order stack holds references to existing nodes, so no node is copied.

Every traversal is O(n) time. The recursive ones use O(h) stack space, and level-order uses O(w), where w is the widest level. A very deep tree (for example 100,000 nodes in a chain) can overflow the thread stack in the recursive versions with StackOverflowError. The iterative in-order version keeps its stack on the heap and does not have this limit.

LeetCode's TreeNode

LeetCode's Java tree problems use the same shape of node, with public fields and constructors for the empty, value-only, and full cases:

Java
import java.util.ArrayList;
import java.util.List;

public class Main {
    static 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;
        }
    }

    static void inOrder(TreeNode root, List<Integer> out) {
        if (root == null) return;
        inOrder(root.left, out);
        out.add(root.val);
        inOrder(root.right, out);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2, new TreeNode(1), new TreeNode(3));
        List<Integer> out = new ArrayList<>();
        inOrder(root, out);
        System.out.println(out);
    }
}
Output
[1, 2, 3]

The algorithms in this lesson work unchanged with that class. The rest of the course uses a TreeNode with the same val, left, and right fields, and null for an empty subtree.

Interview points

  • A BST search, insert, or delete costs O(h): O(log n) when balanced and O(n) when degenerate.
  • In-order traversal of a BST yields sorted values.
  • Deleting a node with two children copies in the in-order successor's value, then deletes the successor.
  • Level-order traversal needs a queue and reads queue.size() once per level.
  • Recursive traversals use O(h) stack, and a skewed tree can cause StackOverflowError.
  • TreeMap and TreeSet are the balanced-tree collections in the Java standard library.

Summary

  • A binary tree node has at most two children; a leaf has none.
  • Height is the number of edges on the longest root-to-leaf path.
  • BST rule: left subtree smaller, right subtree larger (equal values go right here).
  • Pre-order, in-order, and post-order are depth-first; level-order is breadth-first.
  • Java nodes use null for an empty subtree and mutable fields, so no wrapper types are needed.