🔍Intuition

Tree = Family Tree

One ancestor (root) → children → grandchildren. No cycles. Every node has exactly one parent (except root).

HierarchicalOne parentAcyclic

Used in: DOM, file systems, org charts, decision trees, BSTs, heaps

Graph = City Road Map

Cities = nodes, roads = edges. Roads can go one-way or both ways. Can have cycles. No strict parent-child rule.

GeneralAny connectionsMay have cycles

Used in: social networks, GPS routing, web crawlers, dependency graphs

Key Mental Model

Tree is a restricted Graph

Connected + Acyclic + Directed (parent→child)
N nodes → exactly N−1 edges
Always one path between any two nodes

Graph is the general case

Can be connected or disconnected
Can have cycles
Edges can be weighted

📘Definitions

Tree Terminology

Term	Meaning	Example
`root`	Top node, no parent	Node 1 in a tree
`leaf`	Node with no children	Bottom-most nodes
`height`	Longest path from root to leaf	Height of tree above = 2
`depth`	Distance from root to a node	Root has depth 0
`subtree`	A node and all its descendants	Any internal node forms one
`degree`	Number of children a node has	Binary tree: max degree = 2

Tree Types

Binary Tree

Each node has at most 2 children (left, right)

BST

Left < Node < Right — enables O(log n) search

Balanced Tree

Heights of subtrees differ by at most 1 (AVL, Red-Black)

N-ary Tree

Each node can have up to N children

Trie

Tree for string prefixes — each edge = one char

Heap

Complete binary tree with heap property (min/max)

Graph Terminology

Term	Meaning
`vertex / node`	A point in the graph
`edge`	Connection between two vertices
`directed (digraph)`	Edges have direction (A→B ≠ B→A)
`undirected`	Edges go both ways (A—B)
`weighted`	Edges have a cost/weight
`degree`	Number of edges connected to a node
`path`	Sequence of nodes connected by edges
`cycle`	Path that starts and ends at same node
`connected`	Every node reachable from every other
`DAG`	Directed Acyclic Graph — no cycles, ordered

🧠Core Concepts

Graph Representations

Adjacency List (preferred)

graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D'],
  'C': ['A'],
  'D': ['B']
}

Space: O(V+E) — ideal for sparse graphs

Adjacency Matrix

matrix = [
  [0, 1, 1, 0],
  [1, 0, 0, 1],
  [1, 0, 0, 0],
  [0, 1, 0, 0],
]

Space: O(V²) — good for dense graphs

Tree Node Definition

class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

BST Property — Visual Check

When to use which?

Scenario	Use
Hierarchical data (folders, XML)	Tree
Sorted data + fast search/insert	BST
Relationship data (social, maps)	Graph
Shortest path problems	Weighted Graph + BFS/Dijkstra
Dependency ordering	DAG + Topological Sort

⚙️Traversals — Interactive

Tree Traversals — Live Demo

Visit order:

Select a traversal above

In-order (L → Root → R)

def inorder(node):
    if not node:
        return
    inorder(node.left)
    print(node.val)
    inorder(node.right)

BST in-order = sorted output

Pre-order (Root → L → R)

def preorder(node):
    if not node:
        return
    print(node.val)
    preorder(node.left)
    preorder(node.right)

Used to copy/serialize a tree

Post-order (L → R → Root)

def postorder(node):
    if not node:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.val)

Used to delete a tree, calc folder sizes

BFS / Level-order

from collections import deque
def bfs(root):
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.val)
        if node.left: q.append(node.left)
        if node.right: q.append(node.right)

Graph Traversals

DFS — Recursive

def dfs(graph, node, visited=set()):
    if node in visited:
        return
    visited.add(node)
    print(node)
    for neighbor in graph[node]:
        dfs(graph, neighbor, visited)

BFS — Iterative

from collections import deque
def bfs(graph, start):
    visited = set()
    q = deque([start])
    visited.add(start)
    while q:
        node = q.popleft()
        print(node)
        for n in graph[node]:
            if n not in visited:
                visited.add(n)
                q.append(n)

🐍Implementation

Complete BST Implementation

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        self.root = self._insert(self.root, val)

    def _insert(self, node, val):
        if not node:
            return TreeNode(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        return node

    def search(self, val):
        return self._search(self.root, val)

    def _search(self, node, val):
        if not node or node.val == val:
            return node
        if val < node.val:
            return self._search(node.left, val)
        return self._search(node.right, val)

Graph — Build & Traverse

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.adj = defaultdict(list)

    def add_edge(self, u, v, directed=False):
        self.adj[u].append(v)
        if not directed:
            self.adj[v].append(u)

    def dfs(self, start):
        visited, stack = set(), [start]
        result = []
        while stack:
            node = stack.pop()
            if node not in visited:
                visited.add(node)
                result.append(node)
                stack.extend(self.adj[node])
        return result

    def bfs(self, start):
        visited, queue = {start}, deque([start])
        result = []
        while queue:
            node = queue.popleft()
            result.append(node)
            for n in self.adj[node]:
                if n not in visited:
                    visited.add(n)
                    queue.append(n)
        return result

# Usage
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
print(g.dfs('A'))   # ['A', 'C', 'B', 'D']
print(g.bfs('A'))   # ['A', 'B', 'C', 'D']

Detect Cycle in Undirected Graph

def has_cycle(graph, n):
    visited = [False] * n
    def dfs(node, parent):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True  # back edge = cycle!
        return False
    return any(dfs(i, -1) for i in range(n) if not visited[i])

⚡Complexity & Performance

Tree Operations (BST)

Operation	Average	Worst (Unbalanced)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Traversal	O(n)	O(n)
Height	O(log n)	O(n)

Graph Operations

Operation	Adj List	Adj Matrix
Add edge	O(1)	O(1)
Remove edge	O(E)	O(1)
Check edge	O(degree)	O(1)
BFS / DFS	O(V+E)	O(V²)
Space	O(V+E)	O(V²)

Visual: Relative Costs

BST search (balanced)

O(log n)

BST search (skewed)

O(n)

BFS (adj list)

O(V+E)

BFS (adj matrix)

O(V²)

Dijkstra (heap)

O((V+E)logV)

Space Complexity

Recursive DFS: O(h) stack — h = height. Worst case O(n) for skewed tree
BFS queue: O(w) — w = max width. Worst case O(n) for complete tree
Visited set (graph): always O(V)

📊Comparison

DFS vs BFS

Property	DFS	BFS
Data structure	Stack (or recursion)	Queue
Space	O(h) — height	O(w) — width
Finds shortest path?	No (unweighted)	Yes (unweighted)
Complete?	No (infinite graphs)	Yes
Best for	Detect cycle, topo sort, maze	Shortest path, level-by-level
Tree traversal	Pre/In/Post-order	Level-order

Tree Types Comparison

Type	Search	Insert	Ordered?	Use Case
BST	O(log n)*	O(log n)*	Yes	Sorted data
AVL Tree	O(log n)	O(log n)	Yes	Frequent lookups
Heap	O(n)	O(log n)	Partial	Priority queue
Trie	O(k)	O(k)	By char	Autocomplete
Segment Tree	O(log n)	O(log n)	By index	Range queries

* Worst case O(n) if unbalanced

Graph Representation: When to Use?

Adjacency List — Use when:

Graph is sparse (few edges)
Need to iterate over neighbors
Memory is a concern
Most real-world graphs

Adjacency Matrix — Use when:

Graph is dense (many edges)
Need O(1) edge lookup
Floyd-Warshall algorithm
Small number of vertices

🧩Patterns & Use Cases

Pattern: Two-Pass DFS

Run DFS twice to find connected components, bridges, or articulation points (Kosaraju's / Tarjan's)

Pattern: BFS + Distance Array

Maintain dist[] alongside BFS for shortest unweighted paths. Initialize with -1 or infinity.

Pattern: Topological Sort

DAG: use DFS post-order OR Kahn's algorithm (BFS + in-degree). Use for task scheduling, build order.

Pattern: Union-Find

Track connected components efficiently. Use for Kruskal's MST, cycle detection in undirected graphs.

Pattern: Level BFS on Trees

Use a sentinel None or size-based loop to process level by level. Useful for zigzag, average, or right-view problems.

Pattern: Lowest Common Ancestor

Use post-order DFS. Return node when both left and right subtrees find the targets.

Common Interview Patterns

Problem Type	Algorithm	Key Data Structure
Shortest path (unweighted)	BFS	Queue + visited set
Shortest path (weighted)	Dijkstra	Min-heap (heapq)
Minimum spanning tree	Prim's / Kruskal's	Heap / Union-Find
Cycle detection (directed)	DFS with color (white/gray/black)	Visited + recursion stack
Cycle detection (undirected)	DFS with parent tracking	Visited set
Task ordering	Topological Sort	Deque + in-degree array
Tree diameter	DFS twice or single post-order	Global max variable

Dijkstra's — Clean Template

import heapq

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]  # (distance, node)

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

💻Dry Runs

BFS Dry Run — Step by Step

Graph: A-B, A-C, B-D, C-D, D-E    Start: A

BST Insert Dry Run

Insert: 5, 3, 7, 1, 4 into empty BST

Insert	Action	Tree State
5	Root is empty → place at root	5
3	3 < 5 → go left → empty → insert	5(L:3)
7	7 > 5 → go right → empty → insert	5(L:3, R:7)
1	1<5→L; 1<3→L → insert	3(L:1); 5's left subtree
4	4<5→L; 4>3→R → insert	3(L:1, R:4)

In-order result: 1, 3, 4, 5, 7 (sorted!)

Topological Sort Dry Run

Tasks: A→C, B→C, C→D
In-degrees: A=0, B=0, C=2, D=1

Step 1: Queue = [A, B] (in-degree 0)
Step 2: Process A → C's in-degree becomes 1 → order=[A]
Step 3: Process B → C's in-degree becomes 0 → queue=[C] → order=[A,B]
Step 4: Process C → D's in-degree becomes 0 → queue=[D] → order=[A,B,C]
Step 5: Process D → order=[A,B,C,D]

🧠Concept Checks

Test your understanding. Select an answer to reveal the explanation.

🧪Practice Problems

Beginner

1. Maximum Depth of Binary Tree

Return the height of a binary tree.

def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left),
                   maxDepth(root.right))

2. Number of Islands (BFS)

Count connected components of '1's in a 2D grid.

def numIslands(grid):
    count = 0
    def bfs(r, c):
        q = deque([(r, c)])
        grid[r][c] = '0'
        while q:
            row, col = q.popleft()
            for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                nr, nc = row+dr, col+dc
                if 0<=nr

Intermediate

3. Lowest Common Ancestor of BST

def lowestCommonAncestor(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root

4. Course Schedule (Cycle Detection in Directed Graph)

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    for a, b in prerequisites:
        graph[b].append(a)
    # 0=unvisited, 1=in-progress, 2=done
    state = [0] * numCourses
    def dfs(node):
        if state[node] == 1: return False  # cycle!
        if state[node] == 2: return True
        state[node] = 1
        for nei in graph[node]:
            if not dfs(nei): return False
        state[node] = 2
        return True
    return all(dfs(i) for i in range(numCourses))

Advanced

5. Serialize & Deserialize Binary Tree

Hint: Use BFS. Encode None as "null". Split on comma. Rebuild using a queue index.

6. Word Ladder (Shortest Transformation)

Hint: Model as unweighted graph. BFS guarantees shortest path. Use wildcard patterns as intermediate keys.

7. Alien Dictionary (Topological Sort)

Hint: Compare adjacent words to build a directed graph of char ordering. Run topo sort. If cycle, return "".

🚀Interview Tips & Common Mistakes

Top Mistakes to Avoid

Forgetting the visited set in graph traversal → infinite loop in cyclic graphs
Confusing height vs depth — height measured from leaves up, depth from root down
Assuming BST is always balanced — O(log n) is average case, not guaranteed
Not handling disconnected graphs — loop over all nodes, not just from one source
Mutating the graph mid-traversal — use a copy if you mark cells in place
Stack overflow with deep recursion — convert to iterative DFS for production

Key Interview Questions & Approaches

Question	Approach	Complexity
Tree is valid BST?	DFS with min/max bounds	O(n)
Diameter of binary tree	Post-order DFS, track max globally	O(n)
All paths root to leaf	DFS + backtracking with path list	O(n)
Clone graph	BFS + HashMap (old→new node)	O(V+E)
Shortest path in matrix	BFS with 4-directional movement	O(m×n)
Redundant connection	Union-Find	O(n α(n))
Critical connections	Tarjan's bridge-finding DFS	O(V+E)

Quick Interview Checklist

Before you code

Directed or undirected?
Weighted edges?
Can there be cycles?
Connected or disconnected?
What's the expected output — path, bool, count?

Optimization signals

Shortest path → BFS (unweighted), Dijkstra (weighted)
All paths → DFS + backtrack
Ordering → Topological sort
Components → Union-Find or DFS loop
Balance needed → AVL or heapq

Python-specific tips

Use collections.deque for BFS — O(1) popleft vs O(n) for list
Use collections.defaultdict(list) for adjacency lists
Use heapq (min-heap) for Dijkstra — negate values for max-heap
Increase recursion limit: sys.setrecursionlimit(10**5) for deep trees
Use set() for visited — O(1) lookup

Interactive study notes on Graphs and Trees in Python — covering intuition, definitions, traversals, implementations, complexity, and interview tips.

Graphs & Trees in Python