🌳 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

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);
}

📌 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

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);
}

📌 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

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);
}

🔄 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

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);
  }
}

🔁 Summary of Tree Traversals

💡 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