Frontend School
DashboardProblemsLearnPracticeMock InterviewReportsStatsBuy Credits
DashboardProblemsLearnPracticeMock Interview
DSA for Frontend Engineers
  1. 1.Introduction to DSA for Frontend Engineers
  2. 2.JavaScript Fundamentals for DSA
  3. 3.Arrays and Strings: Core Techniques
  4. 4.Objects and Hash Maps in JavaScript
  5. 5.Linked Lists: Building Blocks
  6. 6.Stacks and Queues: LIFO & FIFO
  7. 7.Recursion and Iteration: Problem Solving Paradigms
  8. 8.Introduction to Trees: Binary Trees & BSTs
  9. 9.Tree Traversal Algorithms (BFS & DFS)
  10. 10.Sorting Algorithms I: Basics
  11. 11.Sorting Algorithms II: Divide & Conquer
  12. 12.Searching Algorithms: Linear & Binary Search
  13. 13.Graphs: Representation & Traversals
  14. 14.Dynamic Programming I: Memoization
  15. 15.Heaps and Priority Queues
  16. 16.Tries (Prefix Trees) for Autocomplete & Search
  17. 17.Advanced Graph Algorithms: Shortest Paths & MST
  18. 18.Dynamic Programming II: Tabulation & Frontend Patterns
  19. 19.Frontend System Design with DSA Lens
  20. 20.Interview Strategies & Advanced Problem Solving
DSA for Frontend Engineers
09

DSA · Lesson 9 of 20 · 5 min

Tree Traversal Algorithms (BFS & DFS)

You will be asked to walk a tree. Here’s how to explain your choice of algorithm and write the code.

Choose Your Strategy: Wide or Deep?

When you need to visit every node in a tree, you have two main strategies. The one you choose depends on what you're looking for.

Breadth-First Search (BFS) explores level by level. It visits the root, then all its direct children, then all their children, and so on. Use BFS when you need to find the shortest path between two nodes in an unweighted tree.

Depth-First Search (DFS) explores one branch as far as it can go before backtracking. It goes from the root all the way to a leaf, then backs up to the nearest unexplored path. Use DFS to check if a path between two nodes exists, or to explore all nodes in a particular branch before moving on.

There is no "better" algorithm. The right choice is determined by the structure of the tree and the goal of the traversal.

How to Implement Breadth-First Search (BFS)

The core of BFS is a queue (First-In, First-Out). The algorithm is straightforward: add the root to the queue. While the queue isn't empty, pull a node from the front, "visit" it, and add its children to the back of the queue.

This level-by-level approach is what you need for problems like finding the value of each node at a specific depth, or for a classic like [/problems/binary-tree-level-order-traversal/](Binary Tree Level Order Traversal).

class TreeNode<T> {
  value: T;
  left: TreeNode<T> | null;
  right: TreeNode<T> | null;

  constructor(value: T) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function bfs<T>(root: TreeNode<T> | null): T[] {
  if (!root) {
    return [];
  }

  const result: T[] = [];
  const queue: TreeNode<T>[] = [root];

  while (queue.length > 0) {
    // The '!' tells TypeScript we know queue.length > 0, so shift() won't return undefined.
    const currentNode = queue.shift()!; 
    
    result.push(currentNode.value);

    if (currentNode.left) {
      queue.push(currentNode.left);
    }
    if (currentNode.right) {
      queue.push(currentNode.right);
    }
  }

  return result;
}

The process follows a simple loop driven by the queue.

The trap: Using Array.shift() in JavaScript is an O(N) operation on the array's length. For an interview, this is usually acceptable. In a production environment with very wide trees, the performance hit could be significant. A proper queue implementation using a linked list would provide O(1) dequeues. Mentioning this trade-off shows you think beyond the basic algorithm.

How to Implement Depth-First Search (DFS)

The most common way to implement DFS is with recursion, which uses the call stack as an implicit stack.

For binary trees, DFS has three variations, defined by when you "visit" the current node's value relative to its children.

  1. Pre-order (Root, Left, Right): Visit the node, then recursively visit its left and right children. Use this to create a copy of a tree.
  2. In-order (Left, Root, Right): Visit the left child, then the node itself, then the right child. On a Binary Search Tree, this visits nodes in sorted order.
  3. Post-order (Left, Right, Root): Visit the left and right children before visiting the node itself. Use this to safely delete nodes from a tree, since you process children before their parent.

Here is a standard recursive pre-order traversal. This pattern is essential for problems like checking if one tree is a subtree of another, or for [/problems/path-sum/](Path Sum).

function dfsPreOrder<T>(root: TreeNode<T> | null): T[] {
  const result: T[] = [];

  function traverse(node: TreeNode<T> | null) {
    if (node === null) {
      return;
    }
    result.push(node.value); // Visit current node
    traverse(node.left);     // Traverse left subtree
    traverse(node.right);    // Traverse right subtree
  }

  traverse(root);
  return result;
}

The trap: A very deep tree can cause a stack overflow with a recursive DFS. If you're asked to handle this, the solution is an iterative implementation using your own explicit stack data structure. You replace recursive calls with stack.push().

Complexity: The Trade-off You Must Explain

In an interview, correctly stating the complexity of each approach is non-negotiable.

Time Complexity: O(N) for both BFS and DFS, where N is the number of nodes. You visit each node exactly once.

Space Complexity: This is the critical trade-off.

  • BFS: O(W), where W is the maximum width of the tree. The queue can hold all nodes at the widest level. For a complete binary tree, the last level contains roughly N/2 nodes, making space complexity O(N) in the worst case.
  • DFS: O(H), where H is the maximum height of the tree. This space is used by the call stack (for recursion) or the explicit stack (for iteration). For a skewed tree (essentially a linked list), the height is N, making space complexity O(N) in the worst case.

Your answer should be: "Time is O(N) for both. The space complexity trade-off is between BFS's O(W) and DFS's O(H). I would choose based on the expected shape of the tree."

Connecting Traversal to Frontend Problems

Relate these algorithms to the DOM or component trees. This shows you can apply abstract concepts to your daily work.

BFS is like document.querySelector. It explores siblings at each level before going deeper, finding the "closest" element to the starting point first.

DFS is useful for tasks that require processing entire subtrees, like validating all inputs in a deeply nested form within a component tree. You need to finish one branch of components before moving to the next.

"You have a tree of UI components. Write a function to find the first instance of a Modal component and disable it. Which traversal would you use?"

Use BFS. It guarantees you find the Modal that is highest up in the component tree, which is almost always the one you want. A DFS might find a Modal nested ten levels deep before finding one that is a direct child of the root.

Try it

Given a tree object representing a simple DOM, write a function findImagesWithoutAltText(root) that returns an array of the nodes. Implement it once with BFS and once with DFS. Note the different order of the nodes in the resulting arrays.

Next: We move from tree structures to ordering data with Sorting Algorithms I: Basics.

Lock it in — apply this lesson under interview conditions.

Try a free mock interviewPractice this pattern
Previous

Introduction to Trees: Binary Trees & BSTs

Next

Sorting Algorithms I: Basics