1. Java Collections Overview

Types of Collections:

  1. List:
  2. Set:
  3. Map:

🌳 1. Tree-Specific Collections & Patterns

java
CopyEdit
// 🧱 Tree Node (Binary Tree)
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

// 📍 BFS Traversal — Level Order (uses Queue)
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
    TreeNode node = queue.poll();
    if (node.left != null) queue.offer(node.left);
    if (node.right != null) queue.offer(node.right);
}

// 🧗 DFS Traversal — Preorder/Postorder/Inorder (use Stack or Recursion)
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    // process node
    if (node.right != null) stack.push(node.right);
    if (node.left != null) stack.push(node.left);
}

// 🧮 TreeMap — Sorted Map (Red-Black Tree internally)
TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "Three");  // Sorted by key
treeMap.firstKey();       // Min
treeMap.lastKey();        // Max

// 🧮 TreeSet — Sorted Set (No duplicates, Red-Black Tree)
TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(5);
treeSet.add(1);
treeSet.contains(5);
treeSet.higher(3);  // Smallest > 3

// 📘 PriorityQueue — Min or Max Heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
minHeap.offer(1);
minHeap.poll();  // Removes min

// 🔁 LinkedList as Deque (for Zigzag level order)
Deque<TreeNode> deque = new LinkedList<>();
deque.addFirst(node);  // Acts like Stack
deque.addLast(node);   // Acts like Queue

// 📝 Map<TreeNode, Integer> — For memoizing subtree info
Map<TreeNode, Integer> memo = new HashMap<>();


🔗 2. Graph-Specific Collections & Patterns

java
CopyEdit
// 📍 Graph using Adjacency List
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.putIfAbsent(1, new ArrayList<>());
graph.get(1).add(2);  // Edge from 1 to 2

// 🔁 DFS using Stack
Set<Integer> visited = new HashSet<>();
Stack<Integer> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
    int node = stack.pop();
    if (visited.contains(node)) continue;
    visited.add(node);
    for (int nei : graph.getOrDefault(node, new ArrayList<>())) {
        stack.push(nei);
    }
}

// 🔁 DFS (recursive)
void dfs(int node, Set<Integer> visited) {
    if (!visited.add(node)) return;
    for (int nei : graph.getOrDefault(node, new ArrayList<>())) {
        dfs(nei, visited);
    }
}

// 🚎 BFS using Queue
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
while (!queue.isEmpty()) {
    int node = queue.poll();
    for (int nei : graph.getOrDefault(node, new ArrayList<>())) {
        if (!visited.contains(nei)) {
            visited.add(nei);
            queue.offer(nei);
        }
    }
}

// 🧱 Edge list or weighted graph (for Dijkstra)
class Pair {
    int node, weight;
    Pair(int node, int weight) {
        this.node = node; this.weight = weight;
    }
}
Map<Integer, List<Pair>> weightedGraph = new HashMap<>();
weightedGraph.computeIfAbsent(0, k -> new ArrayList<>()).add(new Pair(1, 5));

// 🛣️ PriorityQueue for Dijkstra’s Algorithm
PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> a.weight - b.weight);

// 🧪 Union-Find (Disjoint Set)
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);  // Path compression
    return parent[x];
}
void union(int a, int b) {
    parent[find(a)] = find(b);
}


🛠️ Utility Java Collections Patterns

java
CopyEdit
// 🔢 Count frequency of elements
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
    freq.put(num, freq.getOrDefault(num, 0) + 1);
}

// 📋 Grouping elements
Map<Integer, List<String>> map = new HashMap<>();
map.computeIfAbsent(3, k -> new ArrayList<>()).add("abc");

// 🔁 Iterate Map
for (Map.Entry<Integer, List<String>> entry : map.entrySet()) {
    int key = entry.getKey();
    List<String> valList = entry.getValue();
}


Time Complexity Summary

Tree Collections