Search

Breath First Search

Breadth First Search (BFS) algorithm traverses a graph in a breadthward motion and uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration.

As in the example given above, BFS algorithm traverses from A to B to E to F first then to C and G lastly to D. It employs the following rules:

• Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.
• If no adjacent vertex is found, remove the first vertex from the queue, and set this vertex as the head.
• Repeat Rule 1 and Rule 2 until the queue is empty.

class BinaryTreeNode:
    def __init__(self, key=None, parent=None, left_child=None, right_child=None):
        self.key = key
        self.parent = parent
        self.left_child = left_child
        self.right_child = right_child

class Tree:
    def __init__(self, tree=None):
        self.root = tree

def bfs(tree):
    from collections import deque
    q = deque()
    q.append(tree)
    while q:
        head = q.popleft()
        print(head.key)
        if head.left_child:
            q.append(head.left_child)
            
        if head.right_child:
            q.append(head.right_child)

Depth First Search

Depth First Search (DFS) algorithm traverses a graph in a depthward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration.

As in the example given above, DFS algorithm traverses from S to A to D to G to E to B first, then to F and lastly to C. It employs the following rules:

• Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.
• If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the vertices from the stack, which do not have adjacent vertices.)
• Repeat Rule 1 and Rule 2 until the stack is empty.

def dfs(tree):
    if not tree.left_child and not tree.right_child:
        print(tree.key)
    else:
        print(tree.key)
        if tree.left_child:
            dfs(tree.left_child)
        
        if tree.right_child:
            dfs(tree.right_child)

def dfs_stack(tree):
    stack = [tree]
    while stack:
        head = stack.pop()
        print(head.key)
        if head.right_child:
            stack.append(head.right_child)
        
        if head.left_child:
            stack.append(head.left_child)

Reference

https://www.tutorialspoint.com/data_structures_algorithms/depth_first_traversal.htm