Trees, Graphs & Heaps in DSA – Complete Guide | Code To Career

Trees, Graphs & Heaps in DSA – Complete Guide

Welcome to CodeToCareer! This comprehensive guide dives deep into three fundamental data structures in Data Structures & Algorithms (DSA): Trees, Graphs, and Heaps. We cover definitions, types, operations, complexity, use cases, and provide code examples in C++, Java, and Python. This SEO‑optimized and AI‑friendly article is designed to help learners, developers, and interview‑prep aspirants alike.

Table of Contents 1. Trees 2. Graphs 3. Heaps 4. Complexity Comparison 5. Applications 6. FAQ 7. Conclusion

1. Trees

A Tree is a hierarchical, non‑linear data structure composed of nodes, with a single root node and subtrees of children, represented as a parent‑child relationship. Trees are widely used in compilers, databases, file systems, and many algorithmic designs.

1.1 Basic Terminology

• Root: the top node
• Leaf: node with no children
• Parent / Child
• Height / Depth: levels
• Edge / Degree

1.2 Common Tree Types

• Binary Tree: each node has max two children
• Binary Search Tree (BST): left subtree nodes ≤ root ≤ right subtree nodes
• AVL Tree: self‑balancing BST
• Red‑Black Tree: color‑balanced BST variant
• Segment Tree: supports range queries
• Trie (Prefix Tree): optimized for string retrieval

1.3 Key Tree Operations

• Insertion / Deletion (BST, AVL, Red‑Black)
• Traversal: Preorder, Inorder, Postorder, Level‑order (BFS)
• Search (BST search takes O(log n) avg.)
• Rotation / Balancing (in AVL & RB Trees)

1.4 Example Code (BST Insert / Search)

// C++ Example
struct Node { int key; Node *left, *right; Node(int k):key(k),left(nullptr),right(nullptr){} };
Node* insert(Node* root, int k) {
  if (!root) return new Node(k);
  if (k < root->key) root->left = insert(root->left, k);
  else root->right = insert(root->right, k);
  return root;
}
bool searchNode(Node* root, int k) {
  if (!root) return false;
  if (root->key == k) return true;
  return (k < root->key) ? searchNode(root->left, k) : searchNode(root->right, k);
}
  

// Java Example
class Node { int key; Node left, right; Node(int k){key=k;}
}
class BST {
  Node root;
  void insert(int k) { root = insertRec(root, k); }
  Node insertRec(Node r, int k) {
    if (r == null) return new Node(k);
    if (k < r.key) r.left = insertRec(r.left, k);
    else if (k > r.key) r.right = insertRec(r.right, k);
    return r;
  }
  boolean search(int k) { return searchRec(root, k); }
  boolean searchRec(Node r, int k) {
    if (r == null) return false;
    if (r.key == k) return true;
    return k < r.key ? searchRec(r.left, k) : searchRec(r.right, k);
  }
}
  

# Python Example
class Node:
    def __init__(self, k): self.key = k; self.left = self.right = None

def insert(root, k):
    if root is None: return Node(k)
    if k < root.key: root.left = insert(root.left, k)
    elif k > root.key: root.right = insert(root.right, k)
    return root

def search(root, k):
    if root is None: return False
    return True if root.key == k else search(root.left, k) if k < root.key else search(root.right, k)
  

1.5 Traversals

Traversals include:

• Inorder (L‑Root‑R): sorted order for BST
• Preorder (Root‑L‑R)
• Postorder (L‑R‑Root)
• Level‑order (Breadth‑First Search using a queue)

2. Graphs

A Graph is a collection of vertices (nodes) and edges connecting pairs. Graphs model relationships: social networks, network routing, maps, and more.

2.1 Graph Terminology

• Vertices**, Edges
• Directed / Undirected
• Weighted / Unweighted
• Adjacency Matrix / List representation
• Path, Cycle, Connected Component

2.2 Traversal Algorithms

Breadth‑First Search (BFS)

Level‑by‑level traversal using a queue. Good for shortest unweighted path.

Depth‑First Search (DFS)

Recursive or stack‑based exploration. Finds components, cycles.

2.3 Shortest Path Algorithms

• Dijkstra’s Algorithm – for weighted directed/undirected graphs without negative weights
• Bellman‑Ford – handles negative weights
• Floyd‑Warshall – all‑pairs shortest path

2.4 Example Code (BFS & DFS)

// C++ BFS & DFS
void BFS(int s, vector>& adj, vector& vis) {
  queue q; vis[s] = true; q.push(s);
  while (!q.empty()) {
    int u = q.front(); q.pop();
    // process node u
    for (int v: adj[u]) {
      if (!vis[v]) { vis[v]=true; q.push(v); }
    }
  }
}

void DFS(int u, vector>& adj, vector& vis) {
  vis[u] = true;
  // process node u
  for (int v: adj[u]) {
    if (!vis[v]) DFS(v, adj, vis);
  }
}
  

// Java BFS & DFS
void bfs(int s, List> adj, boolean[] vis) {
  Queue q = new LinkedList<>();
  vis[s] = true; q.add(s);
  while (!q.isEmpty()) {
    int u = q.remove();
    for (int v: adj.get(u)) {
      if (!vis[v]) { vis[v] = true; q.add(v); }
    }
  }
}

void dfs(int u, List> adj, boolean[] vis) {
  vis[u] = true;
  for (int v: adj.get(u)) if (!vis[v]) dfs(v, adj, vis);
}
  

# Python BFS & DFS
from collections import deque
def bfs(s, adj):
    vis = set([s]); q = deque([s])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in vis:
                vis.add(v); q.append(v)

def dfs(u, adj, vis=None):
    if vis is None: vis = set()
    vis.add(u)
    for v in adj[u]:
        if v not in vis:
            dfs(v, adj, vis)
  

3. Heaps

Heap is a special complete binary tree-based data structure used to implement priority queues. Two main types: Min‑Heap (smallest element at root) and Max‑Heap (largest at root).

3.1 Heap Properties

• Complete binary tree (all levels filled, except possibly last)
• Heap property: parent ≤ children (Min‑Heap), or parent ≥ children (Max‑Heap)

3.2 Heap Operations

• Insert: add element, sift‑up to restore heap
• Extract‑Min / Extract‑Max: remove root, replace with last, sift‑down
• Heapify: build heap from array in O(n)
• Peek: constant time to view root

3.3 Code Examples

// C++ Min‑Heap via STL priority_queue
#include 
using namespace std;
priority_queue, greater> minHeap;
minHeap.push(5);
minHeap.push(2);
int top = minHeap.top(); // 2
minHeap.pop();
  

// Java Min‑Heap via PriorityQueue
import java.util.PriorityQueue;
PriorityQueue minHeap = new PriorityQueue<>();
minHeap.add(5);
minHeap.add(2);
int top = minHeap.peek(); // 2
minHeap.poll();
  

# Python Min‑Heap via heapq
import heapq
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 2)
top = min_heap[0]  # 2
heapq.heappop(min_heap)
  

3.4 Heap Sort Algorithm

Heap Sort uses a heap to sort an array in O(n log n) time. Steps: build max‑heap, repeatedly pop max and rebuild heap.

// C++ Heap Sort
void heapify(vector& a, int n, int i) {
  int largest = i, l = 2*i+1, r = 2*i+2;
  if (la[largest]) largest = l;
  if (ra[largest]) largest = r;
  if (largest!=i) { swap(a[i], a[largest]); heapify(a, n, largest); }
}
void heapSort(vector& a) {
  int n = a.size();
  for (int i=n/2-1; i>=0; --i) heapify(a, n, i);
  for (int i=n-1; i>=0; --i) {
    swap(a[0], a[i]);
    heapify(a, i, 0);
  }
}
  

4. Complexity Comparison

Data Structure	Operation	Time Complexity	Space Complexity
BST (avg)	search/insert/delete	O(log n)	O(n)
AVL / Red‑Black	search/insert/delete	O(log n)	O(n)
BFS/DFS on Graph	traversal	O(V+E)	O(V)
Heap (insert / extract)	priority queue ops	O(log n)	O(n)
Heapify	build heap	O(n)	O(n)
Heap Sort	sort	O(n log n)	O(1) or O(n)

5. Applications

• Trees: implement symbol tables, expression parsing, syntax trees, range queries (segment tree, trie).
• Graphs: networking, path finding, recommendations, clustering, social graphs.
• Heaps: task scheduling, priority queues, event simulation, Dijkstra’s algorithm, heap sort.
• Combined usage: Graph BFS uses a queue from earlier section; Dijkstra uses heap; tree‑based maps in STL/Java.

6. FAQ

Q: How is a binary heap stored?

A: As a contiguous array; left child at 2*i + 1, right at 2*i + 2.

Q: Which tree is better, AVL or Red‑Black?

A: AVL offers stricter balance and faster lookup; Red‑Black offers faster insertion/deletion.

Q: When to use Graph adjacency list vs adjacency matrix?

A: Use adjacency list for sparse graphs (fewer edges), matrix for dense graphs or fast edge‑existence check.

Q: Is Heap Sort stable?

A: No—heap sort is not stable by default.

Q: Can we use heap for median maintenance?

A: Yes—two‑heap method (max‑heap + min‑heap) keeps track of running median efficiently.

7. Conclusion

This guide has walked you through the core of Trees, Graphs, and Heaps in DSA—covering definitions, types, operations, complexity, applications, and practical code examples. You’re now equipped to implement and apply these structures in interviews, projects, or academic challenges.

Remember to revisit this page on CodeToCareer for in‑depth tutorials on other DSA topics like sorting, dynamic programming, and advanced graph algorithms. Happy learning!