Stage 5: Data structures and algorithms, lesson 4 of 5

Trees and graphs

Intermediate3 min read@since 9Code runs on your Java 25
Explain it forThe essentials plus production detail and pitfalls.

Trees have a root and child nodes, with no cycles. A binary search tree (BST) keeps smaller values on the left and larger on the right, so searching is O(log n) when the tree is balanced. TreeMap and TreeSet are self-balancing red-black trees.

Ways to walk a tree:

  • In-order (left, node, right): gives a BST's values in sorted order.
  • Pre-order and post-order: used for copying and deleting trees.
  • Level order (breadth-first), using a queue.

Graphs are nodes connected by edges: social networks, maps, build dependencies. Store them as an adjacency list, Map<String, List<String>>.

  • BFS (a queue) finds the shortest path when every edge counts the same.
  • DFS (a stack or recursion) explores deeply: cycle detection, ordering build steps.
  • Dijkstra (a priority queue) finds shortest paths when edges have weights.

Example

Java
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

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

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

// BFS: fewest introductions between two people
static int degrees(Map<String, List<String>> friends, String from, String to) {
    Queue<String> queue = new ArrayDeque<>(List.of(from));
    Map<String, Integer> dist = new HashMap<>(Map.of(from, 0));
    while (!queue.isEmpty()) {
        String p = queue.poll();
        if (p.equals(to)) return dist.get(p);
        for (String f : friends.getOrDefault(p, List.of())) {
            if (dist.putIfAbsent(f, dist.get(p) + 1) == null) queue.add(f);   // visit once
        }
    }
    return -1;
}

Common mistake

Forgetting to track visited nodes in a graph walk. With a cycle, BFS or DFS loops forever.

Under the hood

An unbalanced BST turns into a linked list (O(n)) if you insert sorted data; balanced trees (red-black, AVL, B-trees) prevent this. Databases index with B+ trees, which keep many keys per node to minimise disk reads; that's what a PostgreSQL index is. Recursion depth equals tree height, so very deep trees need an explicit stack.

Check yourself

Which structure does breadth-first search use?

How this connects

Where this leads

You've reached the end of this thread. Try a learning path for what's next.

Part of Crack the Java interview.

Was this lesson helpful?

Finished reading? Mark it complete to track your progress.