How can you traverse a binary tree?

Traversing a Binary Tree means visiting every node in the tree. There are several ways to do this, typically divided into two approaches: Depth First and Breadth First.

1. Depth First Search (DFS): This approach prioritizes going as deep into the tree as possible. There are three forms of DFS.

- **In-order Traversal**: With this approach, you first visit the left subtree, then the current node, and finally, the right subtree. If we denote nodes by ‘(L, N, R)‘ standing for (Left child, Node, Right child), in-order traversal follows the ‘L-N-R‘ pattern.

- **Pre-order Traversal**: With this approach, you first visit the current node, then the left subtree, and finally, the right subtree. It follows the ‘N-L-R‘ pattern.

- **Post-order Traversal**: With this approach, you first visit the left subtree, then the right subtree, and finally, the current node. It follows the ‘L-R-N‘ pattern.

Here is a Python code example of these traversals for a binary tree.

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def printInorder(root):
    if root:
        printInorder(root.left)
        print(root.val),
        printInorder(root.right)

def printPostorder(root):
    if root:
        printPostorder(root.left)
        printPostorder(root.right)
        print(root.val),

def printPreorder(root):
    if root:
        print(root.val),
        printPreorder(root.left)
        printPreorder(root.right)

2. Breadth First Search (BFS): This approach travels the tree level by level. This is also known as level-order traversal.

A common BFS algorithm is the level-order traversal. It visits each node in level order from left to right. This traversal uses a queue to hold nodes to visit next.

Here is a Python code example of level-order traversal.

from collections import deque

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def printLevelOrder(root):
    if not root:
        return

    queue = deque()
    queue.append(root)

    while queue:
        node = queue.popleft()
        print(node.val),

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

Both DFS and BFS have their uses: DFS is helpful for queries such as "Is there a path to X?", while BFS can answer questions like "What is the shortest (or longest) path to X?".