Tree Search

Deep-First Search

Binary Tree

def binary_tree_dfs(root):
  if root.left:
    binary_tree_dfs(root.left)

  if root.right:
    binary_tree_dfs(root.right)

Tree

def dfs(root):
    if not root:
        return

    visited = set()
    stack = [root]

    while len(stack) > 0:
        n = stack.pop()
        if n is not visited:
            visited.add(n)
            for e in n.children:
                stack.append(e) # push

Breadth-First Search (BFS)

Binary Tree

def binary_tree_bfs(root):
    if not root:
        return

    queue = [root]

    while len(queue) > 0:
        node = queue.pop(0)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

Tree

def bfs(root):
    if not root:
        return

    visited = set()
    queue = [root]

    while len(queue) > 0:
        n = queue.pop(0) # dequeue
        for n in root.childrens:
            if n not in visited:
                explored.add(n)
                queue.append(n) # enqueue