Top Tree and Graph Problems
In this page:
Tree Traversal
Tree traversal visits every node of a tree in a specific, useful order — inorder, preorder, and postorder each visit a node relative to its children differently, and the right choice depends on what the problem actually needs from that order.
Example: Tree Traversal
#include <iostream>
using namespace std;
int val[3] = {2,1,3};
int left[3] = {1,-1,-1}, right[3] = {2,-1,-1};
void inorder(int node) {
if (node == -1) return;
inorder(left[node]);
cout << val[node] << " ";
inorder(right[node]);
}
int main() { inorder(0); return 0; }public class Main {
static int[] val = {2,1,3};
static int[] left = {1,-1,-1}, right = {2,-1,-1};
static void inorder(int node) {
if (node == -1) return;
inorder(left[node]);
System.out.print(val[node] + " ");
inorder(right[node]);
}
public static void main(String[] args) { inorder(0); }
}val = [2,1,3]
left = [1,-1,-1]
right = [2,-1,-1]
def inorder(node):
if node == -1:
return
inorder(left[node])
print(val[node], end=" ")
inorder(right[node])
inorder(0)#include <stdio.h>
int val[3] = {2,1,3};
int left_[3] = {1,-1,-1}, right_[3] = {2,-1,-1};
void inorder(int node) {
if (node == -1) return;
inorder(left_[node]);
printf("%d ", val[node]);
inorder(right_[node]);
}
int main() { inorder(0); return 0; }Login to try C/C++/Java code in the editor
Binary Search Tree
A Binary Search Tree keeps every value in a node's left subtree smaller than the node itself, and every value in its right subtree larger, which is exactly the property that makes search, insert, and delete run in O(log n) on a balanced tree.
Example: Binary Search Tree
#include <iostream>
using namespace std;
int val[3] = {5,3,8};
int left[3] = {1,-1,-1}, right[3] = {2,-1,-1};
bool search(int node, int target) {
if (node == -1) return false;
if (val[node] == target) return true;
return target < val[node] ? search(left[node], target) : search(right[node], target);
}
int main() { cout << "Search 8 in BST: " << (search(0, 8) ? "found" : "not found"); return 0; }public class Main {
static int[] val = {5,3,8};
static int[] left = {1,-1,-1}, right = {2,-1,-1};
static boolean search(int node, int target) {
if (node == -1) return false;
if (val[node] == target) return true;
return target < val[node] ? search(left[node], target) : search(right[node], target);
}
public static void main(String[] args) { System.out.println("Search 8 in BST: " + (search(0, 8) ? "found" : "not found")); }
}val = [5,3,8]
left = [1,-1,-1]
right = [2,-1,-1]
def search(node, target):
if node == -1:
return False
if val[node] == target:
return True
return search(left[node], target) if target < val[node] else search(right[node], target)
print("Search 8 in BST:", "found" if search(0, 8) else "not found")#include <stdio.h>
int val[3] = {5,3,8};
int left_[3] = {1,-1,-1}, right_[3] = {2,-1,-1};
int search(int node, int target) {
if (node == -1) return 0;
if (val[node] == target) return 1;
return target < val[node] ? search(left_[node], target) : search(right_[node], target);
}
int main() { printf("Search 8 in BST: %s", search(0, 8) ? "found" : "not found"); return 0; }Login to try C/C++/Java code in the editor
Graph BFS
Breadth-First Search explores a graph one full level at a time, visiting every neighbor of the current level before moving on to the next level, which makes it the natural choice for finding the shortest path in an unweighted graph.
Example: Graph BFS
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
vector<vector<int>> adj = {{1,2},{0,3},{0,3},{1,2}};
queue<int> q; vector<bool> visited(4,false);
q.push(0); visited[0]=true;
while (!q.empty()) {
int u = q.front(); q.pop(); cout << u << " ";
for (int v : adj[u]) if (!visited[v]) { visited[v]=true; q.push(v); }
}
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
List<List<Integer>> adj = Arrays.asList(Arrays.asList(1,2), Arrays.asList(0,3), Arrays.asList(0,3), Arrays.asList(1,2));
Queue<Integer> q = new LinkedList<>();
boolean[] visited = new boolean[4];
q.add(0); visited[0] = true;
while (!q.isEmpty()) {
int u = q.poll(); System.out.print(u + " ");
for (int v : adj.get(u)) if (!visited[v]) { visited[v] = true; q.add(v); }
}
}
}from collections import deque
adj = [[1,2],[0,3],[0,3],[1,2]]
visited = [False]*4
q = deque([0]); visited[0] = True
while q:
u = q.popleft()
print(u, end=" ")
for v in adj[u]:
if not visited[v]:
visited[v] = True
q.append(v)#include <stdio.h>
int main() {
int adj[4][2] = {{1,2},{0,3},{0,3},{1,2}};
int queue[4], front=0, back=0, visited[4]={0};
queue[back++]=0; visited[0]=1;
while (front < back) {
int u = queue[front++];
printf("%d ", u);
for (int i = 0; i < 2; i++) { int v = adj[u][i]; if (!visited[v]) { visited[v]=1; queue[back++]=v; } }
}
return 0;
}Login to try C/C++/Java code in the editor
Graph DFS
Depth-First Search commits to one path as deep as it can go before backtracking to try alternatives, which makes it well-suited for exploring every possibility, detecting cycles, or finding connected components rather than shortest distances.
Example: Graph DFS
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> adj = {{1,2},{0,3},{0,3},{1,2}};
bool visited[4] = {false};
void dfs(int u) { visited[u] = true; cout << u << " "; for (int v : adj[u]) if (!visited[v]) dfs(v); }
int main() { dfs(0); return 0; }import java.util.*;
public class Main {
static List<List<Integer>> adj = Arrays.asList(Arrays.asList(1,2), Arrays.asList(0,3), Arrays.asList(0,3), Arrays.asList(1,2));
static boolean[] visited = new boolean[4];
static void dfs(int u) { visited[u] = true; System.out.print(u + " "); for (int v : adj.get(u)) if (!visited[v]) dfs(v); }
public static void main(String[] args) { dfs(0); }
}adj = [[1,2],[0,3],[0,3],[1,2]]
visited = [False]*4
def dfs(u):
visited[u] = True
print(u, end=" ")
for v in adj[u]:
if not visited[v]:
dfs(v)
dfs(0)#include <stdio.h>
int adj[4][2] = {{1,2},{0,3},{0,3},{1,2}};
int visited[4] = {0};
void dfs(int u) { visited[u] = 1; printf("%d ", u); for (int i = 0; i < 2; i++) if (!visited[adj[u][i]]) dfs(adj[u][i]); }
int main() { dfs(0); return 0; }Login to try C/C++/Java code in the editor
Shortest Path
Shortest-path algorithms like Dijkstra and Bellman-Ford find the minimum-cost route between vertices in a weighted graph, differing mainly in whether negative edge weights are allowed and how they trade off speed for that extra flexibility.
Example: Shortest Path
#include <iostream>
using namespace std;
int main() {
cout << "Dijkstra: positive weights only, faster; Bellman-Ford: tolerates negative weights, slower";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Dijkstra: positive weights only, faster; Bellman-Ford: tolerates negative weights, slower");
}
}print("Dijkstra: positive weights only, faster; Bellman-Ford: tolerates negative weights, slower")#include <stdio.h>
int main() {
printf("Dijkstra: positive weights only, faster; Bellman-Ford: tolerates negative weights, slower");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 4 topics to unlock
0/4 topics done
Complete these topics first: