You've learned this already. ✅
Click here to view the next lesson.
Chapter 6: Trees and Graphs: Hierarchical Data Structures
Chapter 6: Practical Exercises of Trees and Graphs: Hierarchical Data Structures
For Chapter 6, we have prepared a series of practical exercises. These activities are designed to deepen your understanding of tree and graph data structures, providing hands-on experience in implementing and grasping their key concepts.
Exercise 1: Implement a Binary Search Tree
- Create a basic Binary Search Tree (BST) with methods for insertion and in-order traversal.
- Insert the numbers 10, 5, 15, 2, 5, 13, 22, 1, 14 and then perform an in-order traversal.
Solution:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
new_node = Node(value)
if self.root is None:
self.root = new_node
return
current = self.root
while True:
if value < current.value:
if current.left is None:
current.left = new_node
return
current = current.left
else:
if current.right is None:
current.right = new_node
return
current = current.right
def in_order_traversal(self, node, result=[]):
if node:
self.in_order_traversal(node.left, result)
result.append(node.value)
self.in_order_traversal(node.right, result)
return result
# Test
bst = BinarySearchTree()
for value in [10, 5, 15, 2, 5, 13, 22, 1, 14]:
bst.insert(value)
print(bst.in_order_traversal(bst.root)) # Output: [1, 2, 5, 5, 10, 13, 14, 15, 22]Exercise 2: Implement a Graph using an Adjacency List
- Create a Graph class with methods to add edges and perform a BFS (Breadth-First Search).
- Add edges to connect nodes 0, 1, 2, 3, and 4 in a non-linear fashion and perform a BFS starting from node 0.
Solution:
from collections import defaultdict, deque
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def bfs(self, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
print(vertex, end=' ')
visited.add(vertex)
queue.extend(set(self.graph[vertex]) - visited)
# Test
g = Graph()
edges = [(0, 1), (1, 2), (1, 3), (2, 4)]
for u, v in edges:
g.add_edge(u, v)
g.bfs(0) # Output: 0 1 2 3 4Exercise 3: Depth-First Search (DFS) on a Graph
- Implement DFS for the graph created in Exercise 2.
- Perform a DFS starting from node 0.
Solution:
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph.graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# Test
dfs(g, 0) # Output: 0 1 2 4 3Exercise 4: Implement a Simple Hash Table
- Create a Hash Table class with basic insertion and retrieval methods.
- Insert key-value pairs ('key1', 'value1'), ('key2', 'value2') and retrieve 'key1'.
Solution:
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
def _hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self._hash_function(key)
self.table[index].append((key, value))
def get(self, key):
index = self._hash_function(key)
for k, v in self.table[index]:
if k == key:
return v
return None
# Test
ht = HashTable()
ht.insert('key1', 'value1')
ht.insert('key2', 'value2')
print(ht.get('key1')) # Output: 'value1'Chapter 6: Practical Exercises of Trees and Graphs: Hierarchical Data Structures
For Chapter 6, we have prepared a series of practical exercises. These activities are designed to deepen your understanding of tree and graph data structures, providing hands-on experience in implementing and grasping their key concepts.
Exercise 1: Implement a Binary Search Tree
- Create a basic Binary Search Tree (BST) with methods for insertion and in-order traversal.
- Insert the numbers 10, 5, 15, 2, 5, 13, 22, 1, 14 and then perform an in-order traversal.
Solution:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
new_node = Node(value)
if self.root is None:
self.root = new_node
return
current = self.root
while True:
if value < current.value:
if current.left is None:
current.left = new_node
return
current = current.left
else:
if current.right is None:
current.right = new_node
return
current = current.right
def in_order_traversal(self, node, result=[]):
if node:
self.in_order_traversal(node.left, result)
result.append(node.value)
self.in_order_traversal(node.right, result)
return result
# Test
bst = BinarySearchTree()
for value in [10, 5, 15, 2, 5, 13, 22, 1, 14]:
bst.insert(value)
print(bst.in_order_traversal(bst.root)) # Output: [1, 2, 5, 5, 10, 13, 14, 15, 22]Exercise 2: Implement a Graph using an Adjacency List
- Create a Graph class with methods to add edges and perform a BFS (Breadth-First Search).
- Add edges to connect nodes 0, 1, 2, 3, and 4 in a non-linear fashion and perform a BFS starting from node 0.
Solution:
from collections import defaultdict, deque
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def bfs(self, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
print(vertex, end=' ')
visited.add(vertex)
queue.extend(set(self.graph[vertex]) - visited)
# Test
g = Graph()
edges = [(0, 1), (1, 2), (1, 3), (2, 4)]
for u, v in edges:
g.add_edge(u, v)
g.bfs(0) # Output: 0 1 2 3 4Exercise 3: Depth-First Search (DFS) on a Graph
- Implement DFS for the graph created in Exercise 2.
- Perform a DFS starting from node 0.
Solution:
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph.graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# Test
dfs(g, 0) # Output: 0 1 2 4 3Exercise 4: Implement a Simple Hash Table
- Create a Hash Table class with basic insertion and retrieval methods.
- Insert key-value pairs ('key1', 'value1'), ('key2', 'value2') and retrieve 'key1'.
Solution:
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
def _hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self._hash_function(key)
self.table[index].append((key, value))
def get(self, key):
index = self._hash_function(key)
for k, v in self.table[index]:
if k == key:
return v
return None
# Test
ht = HashTable()
ht.insert('key1', 'value1')
ht.insert('key2', 'value2')
print(ht.get('key1')) # Output: 'value1'Chapter 6: Practical Exercises of Trees and Graphs: Hierarchical Data Structures
For Chapter 6, we have prepared a series of practical exercises. These activities are designed to deepen your understanding of tree and graph data structures, providing hands-on experience in implementing and grasping their key concepts.
Exercise 1: Implement a Binary Search Tree
- Create a basic Binary Search Tree (BST) with methods for insertion and in-order traversal.
- Insert the numbers 10, 5, 15, 2, 5, 13, 22, 1, 14 and then perform an in-order traversal.
Solution:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
new_node = Node(value)
if self.root is None:
self.root = new_node
return
current = self.root
while True:
if value < current.value:
if current.left is None:
current.left = new_node
return
current = current.left
else:
if current.right is None:
current.right = new_node
return
current = current.right
def in_order_traversal(self, node, result=[]):
if node:
self.in_order_traversal(node.left, result)
result.append(node.value)
self.in_order_traversal(node.right, result)
return result
# Test
bst = BinarySearchTree()
for value in [10, 5, 15, 2, 5, 13, 22, 1, 14]:
bst.insert(value)
print(bst.in_order_traversal(bst.root)) # Output: [1, 2, 5, 5, 10, 13, 14, 15, 22]Exercise 2: Implement a Graph using an Adjacency List
- Create a Graph class with methods to add edges and perform a BFS (Breadth-First Search).
- Add edges to connect nodes 0, 1, 2, 3, and 4 in a non-linear fashion and perform a BFS starting from node 0.
Solution:
from collections import defaultdict, deque
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def bfs(self, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
print(vertex, end=' ')
visited.add(vertex)
queue.extend(set(self.graph[vertex]) - visited)
# Test
g = Graph()
edges = [(0, 1), (1, 2), (1, 3), (2, 4)]
for u, v in edges:
g.add_edge(u, v)
g.bfs(0) # Output: 0 1 2 3 4Exercise 3: Depth-First Search (DFS) on a Graph
- Implement DFS for the graph created in Exercise 2.
- Perform a DFS starting from node 0.
Solution:
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph.graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# Test
dfs(g, 0) # Output: 0 1 2 4 3Exercise 4: Implement a Simple Hash Table
- Create a Hash Table class with basic insertion and retrieval methods.
- Insert key-value pairs ('key1', 'value1'), ('key2', 'value2') and retrieve 'key1'.
Solution:
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
def _hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self._hash_function(key)
self.table[index].append((key, value))
def get(self, key):
index = self._hash_function(key)
for k, v in self.table[index]:
if k == key:
return v
return None
# Test
ht = HashTable()
ht.insert('key1', 'value1')
ht.insert('key2', 'value2')
print(ht.get('key1')) # Output: 'value1'Chapter 6: Practical Exercises of Trees and Graphs: Hierarchical Data Structures
For Chapter 6, we have prepared a series of practical exercises. These activities are designed to deepen your understanding of tree and graph data structures, providing hands-on experience in implementing and grasping their key concepts.
Exercise 1: Implement a Binary Search Tree
- Create a basic Binary Search Tree (BST) with methods for insertion and in-order traversal.
- Insert the numbers 10, 5, 15, 2, 5, 13, 22, 1, 14 and then perform an in-order traversal.
Solution:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
new_node = Node(value)
if self.root is None:
self.root = new_node
return
current = self.root
while True:
if value < current.value:
if current.left is None:
current.left = new_node
return
current = current.left
else:
if current.right is None:
current.right = new_node
return
current = current.right
def in_order_traversal(self, node, result=[]):
if node:
self.in_order_traversal(node.left, result)
result.append(node.value)
self.in_order_traversal(node.right, result)
return result
# Test
bst = BinarySearchTree()
for value in [10, 5, 15, 2, 5, 13, 22, 1, 14]:
bst.insert(value)
print(bst.in_order_traversal(bst.root)) # Output: [1, 2, 5, 5, 10, 13, 14, 15, 22]Exercise 2: Implement a Graph using an Adjacency List
- Create a Graph class with methods to add edges and perform a BFS (Breadth-First Search).
- Add edges to connect nodes 0, 1, 2, 3, and 4 in a non-linear fashion and perform a BFS starting from node 0.
Solution:
from collections import defaultdict, deque
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def bfs(self, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
print(vertex, end=' ')
visited.add(vertex)
queue.extend(set(self.graph[vertex]) - visited)
# Test
g = Graph()
edges = [(0, 1), (1, 2), (1, 3), (2, 4)]
for u, v in edges:
g.add_edge(u, v)
g.bfs(0) # Output: 0 1 2 3 4Exercise 3: Depth-First Search (DFS) on a Graph
- Implement DFS for the graph created in Exercise 2.
- Perform a DFS starting from node 0.
Solution:
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph.graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# Test
dfs(g, 0) # Output: 0 1 2 4 3Exercise 4: Implement a Simple Hash Table
- Create a Hash Table class with basic insertion and retrieval methods.
- Insert key-value pairs ('key1', 'value1'), ('key2', 'value2') and retrieve 'key1'.
Solution:
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
def _hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self._hash_function(key)
self.table[index].append((key, value))
def get(self, key):
index = self._hash_function(key)
for k, v in self.table[index]:
if k == key:
return v
return None
# Test
ht = HashTable()
ht.insert('key1', 'value1')
ht.insert('key2', 'value2')
print(ht.get('key1')) # Output: 'value1'