Tree Traversals: BFS and DFS

Tree traversals are a fundamental concept when dealing with binary trees and other hierarchical data structures. Understanding the different traversal strategies allows engineers to navigate trees efficiently, extract meaningful information, and solve complex problems, from pathfinding and hierarchy analysis to serialization and deserialization of tree structures.

At a high level, tree traversals can be categorized into two families: Breadth-First Search (BFS) and Depth-First Search (DFS).

Breadth-First Search (BFS) explores the tree level by level, visiting all nodes at the current depth before moving to the next. This strategy is naturally suited for problems where the notion of "distance from the root" is important, such as finding the shortest path or computing the width of a tree.

Depth-First Search (DFS), on the other hand, explores as far as possible along each branch before backtracking. DFS can be further divided into pre-order, in-order, and post-order traversals, each following a specific visiting order for the root and its subtrees. DFS is ideal for tasks such as tree reconstruction, path calculations, or evaluating hierarchical structures recursively. Its implementation can be either recursive, leveraging the call stack, or iterative, using an explicit stack.

Choosing between BFS and DFS depends on the problem’s nature. BFS provides a natural way to process nodes in increasing depth, while DFS often simplifies recursive reasoning and is memory-efficient for deep but narrow trees when implemented recursively.

In the following sections, we will explore each traversal technique in depth, discussing usage scenarios, TypeScript implementations, and relevant variants, giving you a strong foundation to tackle related coding problems confidently.

For all the example, consider the following TreeNode structure:

interface TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
}

Breadth-First Search (BFS)

As we mentioned before, Breadth-First Search (BFS) on trees processes nodes level by level, starting from the root and moving down to each subsequent depth. This approach is particularly effective when the problem requires knowledge of a node's distance from the root, the width of a tree, or when we want to process nodes in a top-down manner.

The fundamental mechanism behind BFS is the queue, which ensures that nodes are visited in the order they appear on each level. As nodes are dequeued for processing, their children are enqueued, guaranteeing that all nodes at the current level are handled before moving to the next.

BFS is commonly used in scenarios such as:

• Computing tree width or height: By tracking the number of nodes at each level, we can calculate the width of the tree or find the maximum width across all levels.
• Right-side view: Capturing the rightmost node at each level to generate a side view of the tree.
• Zigzag or spiral traversal: Alternating the order of nodes at each level for specific output formats.
• Shortest path in unweighted trees: BFS naturally finds the shortest path from the root to any node due to its level-by-level exploration.

Below you can find the typescript implementation of a BFS traversal that returns the values of nodes level by leve. The implementation traverses the tree iteratively, using a queue to maintain nodes of the current level. Each iteration processes all nodes at one level before moving to the next, preserving the BFS order.

function bfs(root: TreeNode | null): number[][] {
  if (!root) return [];

  const result: number[][] = [];
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel: number[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      currentLevel.push(node.val);

      if (node.left) { 
        queue.push(node.left);
      }

      if (node.right) { 
        queue.push(node.right);
      }   
    }

    result.push(currentLevel);
  }

  return result;
}

Depth-First Search (DFS)

Depth-First Search (DFS) explores a tree by following each branch as deep as possible before backtracking. Unlike BFS, which processes nodes level by level, DFS prioritizes depth, making it especially suitable for recursive reasoning, tree reconstruction, and path-related problems. DFS can be implemented either recursively, leveraging the call stack, or iteratively using an explicit stack.

DFS can be divided into three common traversal strategies: Pre-order, In-order, and Post-order. Each strategy defines a specific visiting order of the root and its subtrees.

Pre-Order Traversal

In pre-order traversal, we visit the root node first, followed by the left subtree, and then the right subtree. This order is particularly useful for tasks such as copying a tree, serializing it, or evaluating hierarchical expressions.

Possible usage scenarios for pre-order traversal include:

• Serializing and deserializing a binary tree.
• Constructing a copy of a tree.
• Path sum problems where root-to-leaf paths are considered.

function preorderDFS(root: TreeNode | null): number[] {
  const result: number[] = [];

  function dfs(node: TreeNode | null) {
    if (!node) {
        return;
    } 

    result.push(node.val);
    
    dfs(node.left);
    dfs(node.right);
  }

  dfs(root);

  return result;
}

function preorderDFSIterative(root: TreeNode | null): number[] {
  if (!root) { 
    return [];
  }
  const stack: TreeNode[] = [root];
  const result: number[] = [];

  while (stack.length > 0) {
    const node = stack.pop()!;
    result.push(node.val);

    if (node.right) { 
      stack.push(node.right);
    }
    if (node.left) { 
      stack.push(node.left);
    }
  }

  return result;
}

In-Order Traversal

In in-order traversal, we visit the left subtree first, then the root node, and finally the right subtree. For binary search trees (BSTs), this traversal produces nodes in sorted order, making it ideal for BST validation and finding the kth smallest element.

Usage Possible usage scenarios for in-order traversal include:

• Validating a BST.
• Finding minimum or kth elements in a BST.
• Implementing BST iterators.

function inorderDFS(root: TreeNode | null): number[] {
  const result: number[] = [];

  function dfs(node: TreeNode | null) {
    if (!node) return;
    dfs(node.left);
    result.push(node.val);
    dfs(node.right);
  }

  dfs(root);

  return result;
}

function inorderDFSIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  const stack: TreeNode[] = [];
  let current: TreeNode | null = root;

  while (current || stack.length > 0) {
    while (current) {
      stack.push(current);
      current = current.left;
    }
    current = stack.pop()!;
    result.push(current.val);
    current = current.right;
  }

  return result;
}

Post-Order Traversal

In post-order traversal, we visit the left subtree first, then the right subtree, and finally the root node. This strategy is particularly effective for tree reconstruction, deletion, or flattening operations where child nodes must be processed before their parent.

Usage Possible usage scenarios for post-order traversal include:

• Deleting nodes and returning a forest.
• Calculating values that depend on child subtrees.
• Flattening a tree into a linked list.

function postorderDFS(root: TreeNode | null): number[] {
  const result: number[] = [];

  function dfs(node: TreeNode | null) {
    if (!node) {
        return;
    }

    dfs(node.left);
    dfs(node.right);
    
    result.push(node.val);
  }

  dfs(root);

  return result;
}

function postorderDFSIterative(root: TreeNode | null): number[] {
  if (!root) return [];
  const stack1: TreeNode[] = [root];
  const stack2: TreeNode[] = [];
  const result: number[] = [];

  while (stack1.length > 0) {
    const node = stack1.pop()!;
    stack2.push(node);

    if (node.left) { 
        stack1.push(node.left);
    }
    if (node.right) {
        stack1.push(node.right);
    }
  }

  while (stack2.length > 0) {
    result.push(stack2.pop()!.val);
  }

  return result;
}

Time and Space Complexity

Understanding the time and space complexity of tree traversals is crucial for choosing the right traversal strategy in coding interviews and real-world applications. While BFS and DFS both visit every node once, their memory requirements differ due to the underlying data structures used for traversal.

Exercises