<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 <h1>Table of Contents<span class="tocSkip"></span></h1>
<div class="toc"><ul class="toc-item"><li><span><a href="#Tree-Data-Structure" data-toc-modified-id="Tree-Data-Structure-1"><span class="toc-item-num">1&nbsp;&nbsp;</span>Tree Data Structure</a></span><ul class="toc-item"><li><span><a href="#Tree-Traversal" data-toc-modified-id="Tree-Traversal-1.1"><span class="toc-item-num">1.1&nbsp;&nbsp;</span>Tree Traversal</a></span><ul class="toc-item"><li><span><a href="#Summary" data-toc-modified-id="Summary-1.1.1"><span class="toc-item-num">1.1.1&nbsp;&nbsp;</span>Summary</a></span></li><li><span><a href="#Implementation" data-toc-modified-id="Implementation-1.1.2"><span class="toc-item-num">1.1.2&nbsp;&nbsp;</span>Implementation</a></span></li></ul></li><li><span><a href="#Binary-Seach-Tree" data-toc-modified-id="Binary-Seach-Tree-1.2"><span class="toc-item-num">1.2&nbsp;&nbsp;</span>Binary Seach Tree</a></span><ul class="toc-item"><li><span><a href="#Summary" data-toc-modified-id="Summary-1.2.1"><span class="toc-item-num">1.2.1&nbsp;&nbsp;</span>Summary</a></span></li></ul></li><li><span><a href="#Heap" data-toc-modified-id="Heap-1.3"><span class="toc-item-num">1.3&nbsp;&nbsp;</span>Heap</a></span><ul class="toc-item"><li><span><a href="#Summary" data-toc-modified-id="Summary-1.3.1"><span class="toc-item-num">1.3.1&nbsp;&nbsp;</span>Summary</a></span></li></ul></li></ul></li></ul></div>
Step2:  Tree Data Structure
Tree Traversal
Resources
Step4:  For depth first search, the list of actions to perform upon each visit to a node
<ASSISTANT_TASK:>
Python Code:
from jupyterthemes import get_themes
from jupyterthemes.stylefx import set_nb_theme
themes = get_themes()
set_nb_theme(themes[1])
%load_ext watermark
%watermark -a 'Ethen' -d -t -v -p jupyterthemes
Explanation: <h1>Table of Contents<span class="tocSkip"></span></h1>
<div class="toc"><ul class="toc-item"><li><span><a href="#Tree-Data-Structure" data-toc-modified-id="Tree-Data-Structure-1"><span class="toc-item-num">1&nbsp;&nbsp;</span>Tree Data Structure</a></span><ul class="toc-item"><li><span><a href="#Tree-Traversal" data-toc-modified-id="Tree-Traversal-1.1"><span class="toc-item-num">1.1&nbsp;&nbsp;</span>Tree Traversal</a></span><ul class="toc-item"><li><span><a href="#Summary" data-toc-modified-id="Summary-1.1.1"><span class="toc-item-num">1.1.1&nbsp;&nbsp;</span>Summary</a></span></li><li><span><a href="#Implementation" data-toc-modified-id="Implementation-1.1.2"><span class="toc-item-num">1.1.2&nbsp;&nbsp;</span>Implementation</a></span></li></ul></li><li><span><a href="#Binary-Seach-Tree" data-toc-modified-id="Binary-Seach-Tree-1.2"><span class="toc-item-num">1.2&nbsp;&nbsp;</span>Binary Seach Tree</a></span><ul class="toc-item"><li><span><a href="#Summary" data-toc-modified-id="Summary-1.2.1"><span class="toc-item-num">1.2.1&nbsp;&nbsp;</span>Summary</a></span></li></ul></li><li><span><a href="#Heap" data-toc-modified-id="Heap-1.3"><span class="toc-item-num">1.3&nbsp;&nbsp;</span>Heap</a></span><ul class="toc-item"><li><span><a href="#Summary" data-toc-modified-id="Summary-1.3.1"><span class="toc-item-num">1.3.1&nbsp;&nbsp;</span>Summary</a></span></li></ul></li></ul></li></ul></div>
End of explanation
# adjacency list can be efficiently represented as
# a python dictionary, where the nodes are the keys
# and the nodes that they are connected to are stored
# as a list of values
graph = {'A': ['B', 'C', 'E'],
         'B': ['A','D', 'E'],
         'C': ['A', 'F', 'G'],
         'D': ['B'],
         'E': ['A', 'B','D'],
         'F': ['C'],
         'G': ['C']}
from collections import deque
def bfs(graph, start):
    Graph traversal using Breadth First Searh
    # keep track of all visited nodes
    visited = set()
    # keep track nodes to be checked
    queue = deque(start)
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            neighbors = graph[node]
            for neighbor in neighbors:
                queue.append(neighbor)
    
    return visited
start = 'A'
bfs(graph, start)
Explanation: Tree Data Structure
Tree Traversal
Resources:
Blog: Demystifying Depth-First Search
Blog: Breaking Down Breadth-First Search
Summary
There are two main ways to traverse through a tree. By traversing, we essentially mean we try to walk through the tree without repeating ourselves.
For depth first search (DFS), we start down a path and we won't stop until we get to the end. In other words, we traverse through one branch of the tree until we get to a leaf and only then will we work back up to the trunk of the tree.
In breadth first search (BFS), we would search through the nodes from one level to the next, and traverse through all the children of a node before moving on to visit the grandchildren nodes
<img src="img/dfs-bfs.png" width="60%" height="60%">
Implementation
Resources:
Blog: How to Implement Breadth-First Search in Python
Blog: Depth-First Search and Breadth-First Search in Python
From an implementation standpoint, the difference between the two is that the breadth first search uses a queue, while depth first search uses a stack.
Breadth First Search (BFS)
We will use a graph that has 7 nodes and 7 edges as our example. The edges are undirected and unweighted. Distance between two nodes will be measured based on the number of edges separating two vertices.
<img src="img/graph1.png" width="50%" height="50%">
When using BFS to traverse through all the nodes in the graph, the algorithm follows the following steps:
Check the starting node and add its neighbours to the queue.
Mark the starting node as explored.
Get the first node from the queue / remove it from the queue.
Check if node has already been visited.
If not, go through the neighbours of the node.
Add the neighbour nodes to the queue.
Mark the node as explored.
Loop through steps 3 to 7 until the queue is empty.
End of explanation
def dfs(graph, start):
    Graph traversal using Depth First Searh
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            neighbors = graph[node]
            for neighbor in neighbors:
                stack.append(neighbor)
    return visited
start = 'A'
dfs(graph, start)
Explanation: For depth first search, the list of actions to perform upon each visit to a node:
Mark the current vertex as being visited.
Explore each adjacent vertex that is not included in the visited set.
End of explanation
<END_TASK>