How do you traverse a binary tree using BFS and DFS?

Python Data Structures - Interview Questions and Answers

Traversing a Binary Tree Using BFS and DFS in Python

Binary trees can be traversed in two main ways:
* Breadth-First Search (BFS) – Level-order traversal
* Depth-First Search (DFS) – Preorder, Inorder, Postorder

1. BFS (Breadth-First Search) – Level Order Traversal

Visits nodes level by level.
Uses a queue (FIFO) data structure.
Time Complexity: O(n)
Space Complexity: O(n) (for storing nodes in the queue).

Implementation of BFS

from collections import deque

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

def bfs(root):
    if not root:
        return
    
    queue = deque([root])  # Initialize queue with root
    while queue:
        node = queue.popleft()  # Remove front node
        print(node.val, end=" ")  # Process node
        
        if node.left:
            queue.append(node.left)  # Add left child
        if node.right:
            queue.append(node.right)  # Add right child

# Example usage
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

bfs(root)  # Output: 1 2 3 4 5 6 7

* Best for shortest path problems & hierarchical data.

2. DFS (Depth-First Search) – Types

DFS explores as deep as possible before backtracking. It can be done in three ways:

a) Preorder (Root → Left → Right)

def dfs_preorder(root):
    if not root:
        return
    print(root.val, end=" ")  # Process root
    dfs_preorder(root.left)   # Process left subtree
    dfs_preorder(root.right)  # Process right subtree

dfs_preorder(root)  # Output: 1 2 4 5 3 6 7

b) Inorder (Left → Root → Right)

def dfs_inorder(root):
    if not root:
        return
    dfs_inorder(root.left)   # Process left subtree
    print(root.val, end=" ")  # Process root
    dfs_inorder(root.right)  # Process right subtree

dfs_inorder(root)  # Output: 4 2 5 1 6 3 7

* Used in Binary Search Trees (BSTs) to get sorted order.

c) Postorder (Left → Right → Root)

def dfs_postorder(root):
    if not root:
        return
    dfs_postorder(root.left)   # Process left subtree
    dfs_postorder(root.right)  # Process right subtree
    print(root.val, end=" ")  # Process root

dfs_postorder(root)  # Output: 4 5 2 6 7 3 1

* Used for deleting nodes safely (e.g., freeing memory).

3. DFS Using a Stack (Iterative)

Since recursion uses the call stack, we can also use an explicit stack.

Preorder DFS (Using a Stack)

def dfs_preorder_iterative(root):
    if not root:
        return
    
    stack = [root]
    while stack:
        node = stack.pop()  # Process current node
        print(node.val, end=" ")
        
        # Push right first so left is processed first (LIFO order)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

dfs_preorder_iterative(root)  # Output: 1 2 4 5 3 6 7

* Useful when recursion depth is too large.

4. BFS vs. DFS – When to Use?

Traversal	Uses
BFS (Level Order)	Shortest path, Networking, AI (e.g., Maze solving)
DFS - Preorder	Copying Trees, Expression Trees
DFS - Inorder	BST Traversal (Sorted Order)
DFS - Postorder	Deleting Trees, Dependency Resolution