Trees and Graphs

From linear to connected

In Arrays and Strings, Linked Lists, and Stacks and Queues, most data had a clear next item: index i + 1, node.next, push/pop, offer/poll.

Now we step into structures where one item can connect to many others.

That unlocks interview classics like:

• folder systems
• organization charts
• HTML/XML structure
• social networks
• maps and routes
• dependency graphs

Today’s goal is not advanced graph algorithms yet. We’ll build the mental model: nodes, edges, trees, graphs, representations, and basic traversal intuition in Java.

A tree is a hierarchy

A tree is made of nodes connected by edges.

Key vocabulary:

• Root: the top node
• Parent: a node with children
• Child: a node below another node
• Leaf: a node with no children
• Subtree: any node plus everything below it

Example:

        A          root
      /   \
     B     C       children of A
    / \
   D   E           leaves: C, D, E

A common interview version is a binary tree, where each node has at most two children: left and right.

Think of a tree as a linked list that learned how to branch.

Visiting a tree by levels

Because you already learned Queues, we can traverse a tree level by level.

This is called level-order traversal:

        10
      /    \
     5      20
    / \       \
   3   7       30

Output: 10 5 20 3 7 30

The idea:

1. Put the root in a queue.
2. Repeatedly remove one node.
3. Print it.
4. Add its children to the queue.

Notice how this builds directly on the queue pattern from Stacks and Queues.

```java
import java.util.*;

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

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

    static void levelOrder(TreeNode root) {
        if (root == null) return;

        Queue<TreeNode> queue = new LinkedList<>();
        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);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(20);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(7);
        root.right.right = new TreeNode(30);

        System.out.print("Level order: ");
        levelOrder(root);
    }
}
```

In a tree, what do we call a node that has no children?

A graph is a network

A graph is also made of nodes and edges, but it does not need a hierarchy.

In graph language:

• Nodes are often called vertices.
• Connections are called edges.
• Edges can be undirected or directed.

Examples:

Undirected friendship:
A --- B
|     |
C --- D

Directed dependency:
Build -> Test -> Deploy

A useful distinction:

• A tree is a connected structure with no cycles and one clear hierarchy.
• A graph is more general: it can have cycles, multiple paths, and no obvious root.

So every tree is graph-like, but not every graph is a tree.

How do we store connections?

In Java interviews, the most common beginner-friendly graph representation is an adjacency list.

It answers one question efficiently:

“Given this node, who are its neighbors?”

Example graph:

0 --- 1
|     |
2 --- 3

Adjacency list:

0: [1, 2]
1: [0, 3]
2: [0, 3]
3: [1, 2]

Why interviewers like it:

• It is simple to build.
• It avoids wasting space on missing edges.
• It works well with queue-based or stack-based traversal.

We’ll study heavier graph algorithms later; for now, focus on representing relationships clearly.

Traversing a graph safely

A graph can contain cycles, so traversal needs one extra idea: visited.

Without visited, you might bounce forever:

0 -> 1 -> 0 -> 1 -> ...

Here is a small breadth-first traversal using a queue. The structure should feel familiar from tree level-order traversal, but graphs require marking nodes we have already seen.

```java
import java.util.*;

public class Main {
    static void bfs(Map<Integer, List<Integer>> graph, int start) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        queue.offer(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(0, 3));
        graph.put(2, Arrays.asList(0, 3));
        graph.put(3, Arrays.asList(1, 2));

        System.out.print("BFS from 0: ");
        bfs(graph, 0);
    }
}
```

True or false: A graph traversal never needs a visited set because each node has only one parent.

Fill in the blank: A common way to store a graph where each node maps to a list of its neighbors is called an ________ list.

What to remember

Trees and graphs are where interview problems start feeling less linear.

Core takeaways:

• A tree models hierarchy: root, parent, child, leaf.
• A binary tree has at most two children per node.
• A graph models general relationships: vertices and edges.
• Graph edges may be directed or undirected.
• An adjacency list is the most common graph representation for coding interviews.
• Queue-based traversal works for both trees and graphs, but graphs usually need visited.

A useful interview question to ask yourself:

“Is this problem about order, hierarchy, or arbitrary relationships?”

If it is hierarchy, think tree. If it is arbitrary connections, think graph.

Next, we’ll return to a more classic interview area: Sorting and Searching, where ordering data efficiently becomes the main theme.