Understanding Depth-First Search (DFS)

In the previous chapter of my React Deep Dive series, we learned that JSX in React is converted into a Fiber tree. This conversion process uses an algorithm similar to DFS to traverse and construct the tree structure. Let's explore how DFS works and why understanding it helps us better comprehend React's rendering process.

What is DFS?

Depth-First Search is a graph/tree traversal algorithm that:

  • Explores as far as possible along each branch before backtracking
  • Uses a stack (either explicit or implicit via recursion)
  • Visits each node exactly once

DFS in Binary Trees

Let's look at a simple binary tree example:

1// Example: Given the tree:
2//       1
3//      / \
4//     2   3
5//    / \
6//   4   5
7
8// DFS Traversal Orders:
9// Pre-order:  1 -> 2 -> 4 -> 5 -> 3
10// In-order:   4 -> 2 -> 5 -> 1 -> 3
11// Post-order: 4 -> 5 -> 2 -> 3 -> 1

Implementing DFS

Let's implement DFS in three ways:

1class TreeNode {
2  constructor(val) {
3      this.val = val;
4      this.left = null;
5      this.right = null;
6  }
7}
8
9// 1. Recursive Pre-order DFS
10function preorderDFS(root) {
11  if (!root) return;
12  
13  console.log(root.val);        // Process current node
14  preorderDFS(root.left);       // Visit left subtree
15  preorderDFS(root.right);      // Visit right subtree
16}
17
18// 2. Recursive Post-order DFS
19function postorderDFS(root) {
20  if (!root) return;
21  
22  postorderDFS(root.left);      // Visit left subtree
23  postorderDFS(root.right);     // Visit right subtree
24  console.log(root.val);        // Process current node
25}
26
27// 3. Recursive In-order DFS
28function inorderDFS(root) {
29  if (!root) return;
30  
31  inorderDFS(root.left);        // Visit left subtree
32  console.log(root.val);        // Process current node
33  inorderDFS(root.right);       // Visit right subtree
34}

Why DFS in React Fiber?

React's Fiber tree construction shares similarities with DFS for several reasons:

  1. Natural Component Hierarchy

    • JSX components form a tree structure
    • DFS naturally follows the component hierarchy
    • Matches how developers think about component relationships

  2. Efficient Tree Construction

    • DFS allows React to process components in a predictable order
    • Helps maintain consistency in tree construction
    • Enables efficient reconciliation

  3. Priority-based Interruption

    • DFS can be paused and resumed at any point
    • Allows React to interrupt low-priority work
    • Enables concurrent rendering

DFS in React Fiber

Here's a simplified version of how React constructs its Fiber tree, which follows a pattern similar to DFS:

1function performUnitOfWork(fiber) {
2  // 1. Begin work on current fiber
3  beginWork(fiber);
4  
5  // 2. Process children (similar to DFS)
6  if (fiber.child) {
7      return fiber.child;
8  }
9  
10  // 3. Process siblings
11  let nextFiber = fiber;
12  while (nextFiber) {
13      // Complete current fiber
14      completeWork(nextFiber);
15      
16      if (nextFiber.sibling) {
17          return nextFiber.sibling;
18      }
19      
20      // Move to parent
21      nextFiber = nextFiber.return;
22  }
23}

Solving LeetCode 200 (Number of Islands)

Let's use DFS to solve a classic problem:

1function numIslands(grid) {
2  if (!grid || !grid.length) return 0;
3  
4  const rows = grid.length;
5  const cols = grid[0].length;
6  let islands = 0;
7  
8  function dfs(r, c) {
9      // Base cases
10      if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') {
11          return;
12      }
13      
14      // Mark as visited
15      grid[r][c] = '0';
16      
17      // Explore all four directions
18      dfs(r + 1, c); // down
19      dfs(r - 1, c); // up
20      dfs(r, c + 1); // right
21      dfs(r, c - 1); // left
22  }
23  
24  // Iterate through grid
25  for (let r = 0; r < rows; r++) {
26      for (let c = 0; c < cols; c++) {
27          if (grid[r][c] === '1') {
28              islands++;
29              dfs(r, c);
30          }
31      }
32  }
33  
34  return islands;
35}
36
37// Example usage:
38const grid = [
39  ['1','1','0','0','0'],
40  ['1','1','0','0','0'],
41  ['0','0','1','0','0'],
42  ['0','0','0','1','1']
43];
44console.log(numIslands(grid)); // Output: 3

Time Complexity

  • For a tree with n nodes: O(n)
  • For a graph with V vertices and E edges: O(V + E)

Space Complexity

  • Recursive DFS: O(h) where h is the height of the tree
  • Iterative DFS: O(w) where w is the maximum width of the tree

Real-World Applications

  1. React Fiber

    • Component tree traversal
    • State updates
    • Reconciliation process

  2. Graph Problems

    • Path finding
    • Cycle detection
    • Topological sorting

  3. Tree Operations

    • Tree validation
    • Tree serialization
    • Tree comparison

Conclusion

DFS is a fundamental algorithm that powers many real-world applications, including React's rendering process. Its ability to traverse tree structures efficiently and its natural fit with component hierarchies make it an ideal choice for React Fiber's implementation.

Understanding DFS helps us better comprehend how React traverses and updates the component tree, leading to more efficient and maintainable applications.