DEV Community

Cover image for ๐ŸŒณ Traversing Binary Trees Like a Pro: DFS vs. BFS Explained Visually
Rakesh Reddy Peddamallu
Rakesh Reddy Peddamallu

Posted on

๐ŸŒณ Traversing Binary Trees Like a Pro: DFS vs. BFS Explained Visually

Now that weโ€™ve covered the basics of binary trees in our first post, it's time to dive into traversalsโ€”the key concept that allows us to visit each node in a tree. Traversing a binary tree is one of the most fundamental operations you'll need when working with trees in real-world applications.

In this post, weโ€™ll break down Depth-First Search (DFS) and Breadth-First Search (BFS) tree traversal algorithms, explain how they work, and show you how to implement them in JavaScript.


๐Ÿค” What is Tree Traversal?

Tree traversal is the process of visiting every node in a tree exactly once in a particular order. Traversal is essential for operations like:

  • Searching: Finding a value or node in the tree.
  • Sorting: In-order traversal on a Binary Search Tree (BST) gives you sorted values.
  • Copying/Serializing: Traversals help with making backups or sending data over a network.

There are two main categories of tree traversal:

  1. Depth-First Search (DFS): Explores as deep as possible down one branch before backtracking.
  2. Breadth-First Search (BFS): Explores all nodes at the present depth level before moving on to nodes at the next level.

๐Ÿ”„ Depth-First Search (DFS)

DFS traversals are typically classified into three types based on the order in which the nodes are visited:

  • In-Order (Left โž Root โž Right)
  • Pre-Order (Root โž Left โž Right)
  • Post-Order (Left โž Right โž Root)

Let's go through each one!


๐Ÿ“Œ 1. In-Order Traversal (Left โž Root โž Right)

In in-order traversal, the process is to visit:

  1. The left child
  2. The current node (root)
  3. The right child

This order is especially useful for Binary Search Trees (BSTs) because it visits nodes in ascending order.

Example:

For the following tree:

       10
      /  \
     5    15
    / \     \
   3   7     20
Enter fullscreen mode Exit fullscreen mode

In-order traversal would visit the nodes in this order: 3, 5, 7, 10, 15, 20.

Code for In-Order Traversal:

function inOrder(node) {
  if (!node) return;
  inOrder(node.left);
  console.log(node.value);
  inOrder(node.right);
}
Enter fullscreen mode Exit fullscreen mode

๐Ÿ“Œ 2. Pre-Order Traversal (Root โž Left โž Right)

In pre-order traversal, the order is:

  1. Visit the current node (root)
  2. Visit the left child
  3. Visit the right child

Pre-order is often used when you want to copy a tree or serialize it.

Example:

For the tree:

       10
      /  \
     5    15
    / \     \
   3   7     20
Enter fullscreen mode Exit fullscreen mode

Pre-order traversal visits the nodes in this order: 10, 5, 3, 7, 15, 20.

Code for Pre-Order Traversal:

function preOrder(node) {
  if (!node) return;
  console.log(node.value);
  preOrder(node.left);
  preOrder(node.right);
}
Enter fullscreen mode Exit fullscreen mode

๐Ÿ“Œ 3. Post-Order Traversal (Left โž Right โž Root)

In post-order traversal, the order is:

  1. Visit the left child
  2. Visit the right child
  3. Visit the current node (root)

Post-order is commonly used in applications like deleting a tree or evaluating expression trees.

Example:

For the tree:

       10
      /  \
     5    15
    / \     \
   3   7     20
Enter fullscreen mode Exit fullscreen mode

Post-order traversal visits the nodes in this order: 3, 7, 5, 20, 15, 10.

Code for Post-Order Traversal:

function postOrder(node) {
  if (!node) return;
  postOrder(node.left);
  postOrder(node.right);
  console.log(node.value);
}
Enter fullscreen mode Exit fullscreen mode

๐Ÿ”„ Breadth-First Search (BFS)

Unlike DFS, which goes deep down one branch, Breadth-First Search (BFS) explores the tree level by level.

  • Start at the root.
  • Visit all nodes at the current level.
  • Move to the next level, visiting all its nodes, and repeat.

This is particularly useful for finding the shortest path in unweighted trees or graphs.

Example:

For the tree:

       10
      /  \
     5    15
    / \     \
   3   7     20
Enter fullscreen mode Exit fullscreen mode

BFS (Level-order) traversal visits the nodes in this order: 10, 5, 15, 3, 7, 20.

Code for BFS (Level-Order Traversal):

function levelOrder(root) {
  if (!root) return;
  const queue = [root];

  while (queue.length) {
    const current = queue.shift();
    console.log(current.value);

    if (current.left) queue.push(current.left);
    if (current.right) queue.push(current.right);
  }
}
Enter fullscreen mode Exit fullscreen mode

๐Ÿ” Summary of Tree Traversals

Traversal Type Order Use Cases Example Output
In-Order Left โž Root โž Right Sorted values in BST, printing 3, 5, 7, 10, 15, 20
Pre-Order Root โž Left โž Right Copying, serializing trees 10, 5, 3, 7, 15, 20
Post-Order Left โž Right โž Root Deleting, evaluating expressions 3, 7, 5, 20, 15, 10
BFS (Level-Order) Level by Level Shortest path, level-based searches 10, 5, 15, 3, 7, 20

๐Ÿ’ก When to Use Which Traversal?

  • In-order: When you need sorted output (e.g., in BSTs).
  • Pre-order: When you need to copy or serialize the tree.
  • Post-order: For deletion or bottom-up evaluation.
  • BFS: When you need to process the tree level by level (e.g., shortest path, finding the height).

๐Ÿš€ Wrapping Up

In this post, we covered depth-first search (DFS) and breadth-first search (BFS) tree traversal algorithms. You now have the foundational knowledge to:

  • Implement tree traversals in JavaScript
  • Understand when and why to use different traversal methods

Top comments (0)