Core Concepts and Queue Usage

Breadth-First Search (BFS) is fundamental for traversing graphs and trees, particularly useful for level order traversal, identifying connected components, topological sorting, and finding the shortest path in unweighted graphs (where all edges possess a length of 1).

When implementing BFS, utilize a queue to track nodes at the current depth. ArrayDeque or LinkedList are preferred over ArrayList due to performance overhead in array shifting. Use offer() to enqueue and poll() to dequeue, avoiding add() and pop() which throw exceptions upon failure.

Tree Traversal and Serialization

Level Order Traversal

To traverse a binary tree level by level, enqueue the root and process nodes iteratively, adding child nodes to the queue for the next iteration.

java public List<List<Integer>> traverseByLevel(TreeNode current) { List<List<Integer>> outcome = new ArrayList<>(); if (current == null) return outcome;

Deque<TreeNode> nodeQueue = new ArrayDeque<>();
nodeQueue.offer(current);

while (!nodeQueue.isEmpty()) {
    int levelSize = nodeQueue.size();
    List<Integer> currentLevelValues = new ArrayList<>();
    for (int i = 0; i < levelSize; i++) {
        TreeNode poppedNode = nodeQueue.poll();
        currentLevelValues.add(poppedNode.val);
        if (poppedNode.left != null) nodeQueue.offer(poppedNode.left);
        if (poppedNode.right != null) nodeQueue.offer(poppedNode.right);
    }
    outcome.add(currentLevelValues);
}
return outcome;

}

Data Serialization

Serialization converts structured in-memory objects into a string format, essential for persistent storage (preventing data loss on power off) and network transmission (machines cannot read each other's memory). Deserialization reconstructs objects from strings. Common formats include JSON, XML, Thrift, and ProtoBuf, balancing compression rate against human readability.

Binary Tree Serialization

BFS offers an intuitive way to serialize binary trees, making it straightforward to visualize the tree structure upon deserializasion.

java public String convertTreeToString(TreeNode root) { if (root == null) return "{}"; List<TreeNode> nodeList = new ArrayList<>(); nodeList.add(root); for (int idx = 0; idx < nodeList.size(); idx++) { TreeNode curr = nodeList.get(idx); if (curr == null) continue; nodeList.add(curr.left); nodeList.add(curr.right); } while (nodeList.get(nodeList.size() - 1) == null) { nodeList.remove(nodeList.size() - 1); } StringBuilder builder = new StringBuilder("{"); builder.append(nodeList.get(0).val); for (int idx = 1; idx < nodeList.size(); idx++) { builder.append(","); builder.append(nodeList.get(idx) == null ? "#" : nodeList.get(idx).val); } builder.apppend("}"); return builder.toString(); }

public TreeNode restoreTreeFromString(String str) { if (str.equals("{}")) return null; String[] components = str.substring(1, str.length() - 1).split(","); List<TreeNode> nodes = new ArrayList<>(); TreeNode rootNode = new TreeNode(Integer.parseInt(components[0])); nodes.add(rootNode); int parentIdx = 0; boolean isLeftChild = true; for (int idx = 1; idx < components.length; idx++) { if (!components[idx].equals("#")) { TreeNode child = new TreeNode(Integer.parseInt(components[idx])); if (isLeftChild) nodes.get(parentIdx).left = child; else nodes.get(parentIdx).right = child; nodes.add(child); } if (!isLeftChild) parentIdx++; isLeftChild = !isLeftChild; } return rootNode; }

Graph Traversal and Algorithms

Graph are typically represented using an adjacency list, such as Map<Integer, Set<Integer>>, mapping a node to its connected neighbors.

Graph Valid Tree

A graph forms a valid tree if it satisfies two conditions: the number of edges is exactly one less than the number of nodes, and all nodes are fully connected (reachable from any starting point).

java public boolean isTree(int nodeCount, int[][] edgeList) { if (nodeCount == 0) return false; if (edgeList.length != nodeCount - 1) return false;

Map<Integer, Set<Integer>> adjacencyMap = buildGraph(nodeCount, edgeList);
Set<Integer> visited = new HashSet<>();
Deque<Integer> processingQueue = new ArrayDeque<>();
processingQueue.offer(0);
visited.add(0);

while (!processingQueue.isEmpty()) {
    int curr = processingQueue.poll();
    for (int adj : adjacencyMap.get(curr)) {
        if (visited.contains(adj)) continue;
        visited.add(adj);
        processingQueue.offer(adj);
    }
}
return visited.size() == nodeCount;

}

private Map<Integer, Set<Integer>> buildGraph(int nodeCount, int[][] edgeList) { Map<Integer, Set<Integer>> graph = new HashMap<>(); for (int i = 0; i < nodeCount; i++) graph.put(i, new HashSet<>()); for (int[] edge : edgeList) { graph.get(edge[0]).add(edge[1]); graph.get(edge[1]).add(edge[0]); } return graph; }

Graph Cloning

Cloning an undirected graph involves three distinct steps: use BFS to gather all original nodes, clone the nodes while maintaining a mapping from original to clone, and finally copy the edges (neighbors) based on the mapping.

java public UndirectedGraphNode copyGraph(UndirectedGraphNode startNode) { if (startNode == null) return null; List<UndirectedGraphNode> allNodes = gatherNodes(startNode); Map<UndirectedGraphNode, UndirectedGraphNode> cloningMap = new HashMap<>(); for (UndirectedGraphNode orig : allNodes) { cloningMap.put(orig, new UndirectedGraphNode(orig.label)); } for (UndirectedGraphNode orig : allNodes) { UndirectedGraphNode copy = cloningMap.get(orig); for (UndirectedGraphNode adj : orig.neighbors) { copy.neighbors.add(cloningMap.get(adj)); } } return cloningMap.get(startNode); }

private List<UndirectedGraphNode> gatherNodes(UndirectedGraphNode startNode) { Deque<UndirectedGraphNode> queue = new ArrayDeque<>(); Set<UndirectedGraphNode> seen = new HashSet<>(); queue.offer(startNode); seen.add(startNode); while (!queue.isEmpty()) { UndirectedGraphNode curr = queue.poll(); for (UndirectedGraphNode adj : curr.neighbors) { if (!seen.contains(adj)) { seen.add(adj); queue.offer(adj); } } } return new ArrayList<>(seen); }

Topological Sorting

To perform topological sorting on a directed graph, calculate the in-degree (number of incoming edges) for each node. Nodes with an in-degree of zero act as starting points. Enqueue these root nodes, then iteratively remove them from the graph by decreasing the in-degree of their neighbors. When a neighbor's in-degree reaches zero, enqueue it.

java public ArrayList<DirectedGraphNode> getTopologicalOrder(ArrayList<DirectedGraphNode> graphNodes) { ArrayList<DirectedGraphNode> sortedList = new ArrayList<>(); Map<DirectedGraphNode, Integer> incomingEdges = new HashMap<>(); for (DirectedGraphNode node : graphNodes) { for (DirectedGraphNode adj : node.neighbors) { incomingEdges.put(adj, incomingEdges.getOrDefault(adj, 0) + 1); } } Deque<DirectedGraphNode> queue = new ArrayDeque<>(); for (DirectedGraphNode node : graphNodes) { if (!incomingEdges.containsKey(node)) { queue.offer(node); sortedList.add(node); } } while (!queue.isEmpty()) { DirectedGraphNode curr = queue.poll(); for (DirectedGraphNode adj : curr.neighbors) { incomingEdges.put(adj, incomingEdges.get(adj) - 1); if (incomingEdges.get(adj) == 0) { sortedList.add(adj); queue.offer(adj); } } } return sortedList; }

Complexity: Graphs vs. Matrices

For a graph containing $N$ vertices and $M$ edges, the maximum value of $M$ is $O(N^2)$. Consequently, the time complexity for BFS on a graph is $O(M)$, reaching $O(N^2)$ in the worst-case scenario.

In an $N \times M$ matrix, there are $N \times M$ cells and approximately $N \times M \times 2$ edges (each cell connects to four adjacent cells, and each edge is shared by two cells). Therefore, the time complexity for BFS on a matrix is $O(N \times M)$.