Part $1$: Trees $(50$ Points$)$

Trees are hierarchical data structures with a root node and child nodes. In this assignment, we'll

work with binary trees, which are trees where each node has at most two children.

$1.$ Basic Tree Operations $(20$ Points$)$

You will create a simple binary tree that supports three main operations: inserting nodes,

searching for a specific value, and deleting a node.

Example :

If you insert the values $`10,5,15,2,7`$ into the binary tree, the tree should look like this:

$```$

$10$

$/\backslash$

$515$

$/\backslash$

$27$

$```$

Tasks :

$-$ Write a function to insert nodes $(7$ Points$).$

$-$ Write a function to search for a value in the tree $(6$ Points$).$

$-$ Write a function to delete a node from the tree $(7$ Points$).$

Hints :

$-$ For insertion, start from the root and find the correct position for the new node.

$-$ For searching, traverse the tree and return $`$True$`$ if the value is found, else return $`$False$`.$

$-$ For deletion, handle three cases: leaf node deletion, node with one child, and node with two

children.

$2.$ Tree Traversals $(15$ Points$)$

Tree traversal means visiting all the nodes in a particular order. You$$ll write code to visit nodes in

three different ways: Preorder, Inorder, and Postorder.

Example :

For the tree above, the traversals will look like:

$-$ Preorder $($root$-$left$-$right$)$: $`10,5,2,7,15`$

$-$ Inorder $($left$-$root$-$right$)$: $`2,5,7,10,15`$

$-$ Postorder $($left$-$right$-$root$)$: $`2,7,5,15,10`$

Tasks :

$-$ Write a function for Preorder traversal $(5$ Points$).$

$-$ Write a function for Inorder traversal $(5$ Points$).$

$-$ Write a function for Postorder traversal $(5$ Points$).$

$3.$ Height and Depth of a Tree $(15$ Points$)$

The height of a tree is the longest path from the root to a leaf. The depth of a node is how far

it is from the root.

Example :

In the above tree, the height of the tree is $`2`,$ and the depth of node $`7`$ is $`2`($because you

move two levels from the root to reach $`7`).$

Tasks :

$-$ Write a function to calculate the height of the tree $(7$ Points$).$

$-$ Write a function to calculate the depth of a specific node $(8$ Points$).$

$---$

Part $2$: Graphs $(50$ Points$)$

Graphs are made of nodes $($or vertices$)$ connected by edges. We$$ll represent a graph using an

adjacency list, which is a simple way of showing which nodes are connected.

$1.$ Graph Representation $(20$ Points$)$

You$$ll write a Python class to create a graph using an adjacency list. This will help us represent

connections between different nodes.

Example :

If you have the following edges:

$`($A$,$ B$),($A$,$ C$),($B$,$ D$),($C$,$ D$)`,$

the adjacency list will look like this:

$```$

A: $[$B$,$ C$]$

B: $[$D$]$

C: $[$D$]$

D: $[]$

$```$

Tasks :

$-$ Write a function to add a vertex $(5$ Points$).$

$-$ Write a function to add an edge between two vertices $(5$ Points$).$

$-$ Write a function to display the adjacency list $(5$ Points$).$

$-$ Test your functions by creating a simple graph and displaying it $(5$ Points$).$

$2.$ Graph Traversals $(15$ Points$)$

Just like trees, you can traverse graphs. The two most common methods are Depth$-$First Search

$($DFS$)$ and Breadth$-$First Search $($BFS$).$

Example :

For the graph above, starting from node $`$A$`,$ the traversals will look like this:

$-$ DFS: $`$A $->$ B $->$ D $->$ C$`$

$-$ BFS: $`$A $->$ B $->$ C $->$ D$`$

Tasks :

$-$ Write a function for DFS $(7$ Points$).$

$-$ Write a function for BFS $(8$ Points$).$

$3.$ Detecting Cycles in a Graph $(15$ Points$)$

A cycle in a graph occurs when you can start at a node, travel along edges, and return to the

same node. You will write a function to detect cycles in both directed and undirected graphs.

Tasks :

$-$ Write a function to detect cycles in an undirected graph $(7$ Points$).$

$-$ Write a function to detect cycles in a directed graph $(8$ Points