Python DSA: Trees and Graphs Coding Problems

Trees and graphs are advanced data structures frequently asked in coding interviews. Understanding traversal techniques and problem-solving strategies is essential.

This tutorial covers important coding problems related to binary trees and graphs using Python.

1. Binary Tree Basics

              
            
Python

          Binary tree node structure
        
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

2. Tree Traversal (DFS)

Inorder Traversal

              
            
Python

          Inorder traversal
        
def inorder(root):
    if root:
        inorder(root.left)
        print(root.data, end=' ')
        inorder(root.right)

Preorder Traversal

              
            
Python

          Preorder traversal
        
def preorder(root):
    if root:
        print(root.data, end=' ')
        preorder(root.left)
        preorder(root.right)

Postorder Traversal

              
            
Python

          Postorder traversal
        
def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.data, end=' ')

3. Breadth First Search (Level Order)

              
            
Python

          BFS traversal
        
from collections import deque

def bfs(root):
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.data, end=' ')
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

4. Tree Coding Problems

Problem 1: Height of Binary Tree

              
            
Python

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

Problem 2: Count Nodes

              
            
Python

          Count nodes
        
def count_nodes(root):
    if not root:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

Problem 3: Check Balanced Tree

              
Python

          Balanced tree
        
def is_balanced(root):
    if not root:
        return True

    lh = height(root.left)
    rh = height(root.right)

    return abs(lh - rh) <= 1 and is_balanced(root.left) and is_balanced(root.right)

5. Graph Representation

              
            
Python

          Adjacency list
        
graph = {
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [3]
}

6. Depth First Search (DFS)

              
            
Python

          DFS graph
        
def dfs(graph, node, visited):
    if node not in visited:
        print(node, end=' ')
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

visited = set()
dfs(graph, 0, visited)

7. Breadth First Search (Graph)

              
            
Python

          BFS graph
        
from collections import deque

def bfs(graph, start):
    visited = set()
    q = deque([start])

    while q:
        node = q.popleft()
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            q.extend(graph[node])

8. Graph Coding Problems

Problem 4: Detect Cycle (DFS)

              
            
Python

          Cycle detection
        
def has_cycle(graph, node, visited, parent):
    visited.add(node)

    for neighbor in graph[node]:
        if neighbor not in visited:
            if has_cycle(graph, neighbor, visited, node):
                return True
        elif neighbor != parent:
            return True

    return False

Problem 5: Shortest Path (BFS)

              
            
Python

          Shortest path
        
from collections import deque

def shortest_path(graph, start, end):
    q = deque([(start, 0)])
    visited = set()

    while q:
        node, dist = q.popleft()
        if node == end:
            return dist
        if node not in visited:
            visited.add(node)
            for neighbor in graph[node]:
                q.append((neighbor, dist + 1))

9. Tips for Trees & Graphs

1. Master DFS and BFS patterns.

2. Use recursion wisely.

3. Track visited nodes in graphs.

4. Understand time and space complexity.

10. Practice Problems

1. Lowest Common Ancestor.

2. Diameter of Tree.

3. Topological Sort.

4. Dijkstra’s Algorithm.

5. Number of Islands problem.

Conclusion

Trees and graphs are critical topics in data structures and algorithms. Mastering traversal techniques and solving problems regularly will significantly improve your coding skills.

Practice consistently and explore advanced algorithms to excel in interviews.