Binary Search Trees: The Knights of Data Kingdom - Part 3

Part 10 of data structures series. Let’s discover the fascinating world of BST traversal algorithms (in-order, pre-order, post-order, level-order).

Ahoy, brave coder! 🏰 Welcome back to the magical land of the Data Kingdom. In our previous adventures, you met the Binary Search Tree Knights—valiant guardians of sorted data. But today, you embark on an even more exciting quest: a Tree Traversal Treasure Hunt! 🌳💎

The treasure lies hidden deep within the Binary Search Tree, and to find it, you must learn the ancient arts of tree traversal. With each method, you’ll explore different paths through the tree. Along the way, you’ll discover treasures (data) by walking through In-Order, Pre-Order, Post-Order, and Level-Order trails!

Ready? Let’s begin our adventure! ⚔️

Chapter 1: BST - Your Map of the Kingdom 🗺

Before you can start exploring, you’ll need a map—a Binary Search Tree (BST) to guide you. Let’s quickly set up our kingdom’s map (In the previous article, we covered how to build it—be sure to check it out if you haven't already!):

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  // A helper method to insert new values into the tree
  insert(value) {
    const newNode = new Node(value);
    if (!this.root) {
      this.root = newNode; // The root is where it all starts
    } else {
      this.insertNode(this.root, newNode);
    }
  }

  // Recursive function to find the right spot for the node
  insertNode(current, newNode) {
    if (newNode.value < current.value) {
      if (!current.left) {
        current.left = newNode;
      } else {
        this.insertNode(current.left, newNode);
      }
    } else {
      if (!current.right) {
        current.right = newNode;
      } else {
        this.insertNode(current.right, newNode);
      }
    }
  }
}

// Let's build the kingdom's BST!
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(6);
bst.insert(15);
bst.insert(3);
bst.insert(8);
bst.insert(20);

// Your map is ready! The root starts at node 10.
    10
   /  \
  6    15
 / \    \
3   8   20

Now that we have our map, let’s set off on our treasure hunt. 💎 Each traversal method represents a unique path through the kingdom. Our mission is to visit each node (castle) and collect treasures (node values).

---

Chapter 2: In-Order Traversal - The Path of Sorting

Your first quest begins on the Path of Sorting. The ancient scholars of the Data Kingdom said that this path reveals treasures in ascending order.

Think of it like visiting the leftmost castle first, then the current castle, and finally the right castle.

    10
   /  \
  6    15
 / \    \
3   8   20

// The result should look like this (in-order/sorted): 3 6 8 10 15 20

The result should look like this: 3 6 8 10 15 20

Here’s the magic spell (code) for In-Order Traversal:

function inOrder(node) {
  if (node !== null) {
    inOrder(node.left); // First, visit the left castle (node)
    console.log(node.value); // Then, collect treasure from the current castle
    inOrder(node.right); // Finally, visit the right castle
  }
}

console.log("In-Order Treasures:");
inOrder(bst.root);  // Start the quest from the root of the tree

Result:

In-Order Treasures: 
3 6 8 10 15 20

Ah, look at that! You’ve collected the treasures in sorted order. 🎉 Not only is this a great way to explore, but it’s also the secret behind tree-based sorting techniques.

Where to use (real life scenarios):

• Sorting data.

• Displaying a hierarchy (like a family tree or a directory structure) in a structured, ordered way.

---

Chapter 3: Pre-Order Traversal - The King's Path

Next up, you’ll walk the King's Path—a direct route where you visit the current castle (node) first, then the left castle, and finally the right castle.

Here’s your pre-order traversal spell:

function preOrder(node) {
  if (node !== null) {
    console.log(node.value); // First, collect treasure from the current castle
    preOrder(node.left); // Then, visit the left castle
    preOrder(node.right); // Finally, visit the right castle
  }
}

console.log("Pre-Order Treasures:");
preOrder(bst.root);  // Start the quest from the root of the tree

Result:

Pre-Order Treasures:
10 6 3 8 15 20

The King’s Path is perfect for building a tree from scratch or when you need to save the entire kingdom's layout into a scroll (file). 📜

Where to use (real life scenarios):

• Exporting a tree structure (e.g., copying a file directory).

• Prefix expressions in calculators (like when evaluating or printing mathematical expressions).

---

Chapter 4: Post-Order Traversal - The Scout's Journey

Ah, but the most cautious travelers—like the royal scouts—take the Scout's Journey. They explore all the surroundings before reporting back to the current castle.

In post-order traversal, we visit the left castle, then the right castle, and only after that do we collect treasure from the current castle.

Here’s your post-order traversal spell:

function postOrder(node) {
  if (node !== null) {
    postOrder(node.left);  // First, visit the left castle
    postOrder(node.right); // Then, visit the right castle
    console.log(node.value); // Finally, collect treasure from the current castle
  }
}

console.log("Post-Order Treasures:");
postOrder(bst.root);  // Start the quest from the root of the tree

Result:

Post-Order Treasures:
3 8 6 20 15 10

This path is useful for tearing down the kingdom (tree) when the knights need to rebuild from scratch or when freeing up memory! 💣

Where to use (real life scenarios):

• Deleting a tree (freeing up memory after processing).

• Postfix expressions in calculators (evaluating complex operations).

---

Chapter 5: Level-Order Traversal - The Royal Parade

Finally, behold the Royal Parade! 👑 In this quest, you visit each castle level by level, starting from the top. This is also known as Breadth-First Search (BFS).

Let’s bring out the big spell book for this one:

function levelOrder(node) {
  if (!node) return;
  const queue = [];
  queue.push(node);

  while (queue.length > 0) {
    let current = queue.shift(); // Visit the current castle (node)
    console.log(current.value); // Collect treasure
    if (current.left) queue.push(current.left); // Enqueue the left castle
    if (current.right) queue.push(current.right); // Enqueue the right castle
  }
}

console.log("Level-Order Treasures:");
levelOrder(bst.root);  // Start the parade from the root of the tree

Result:

Level-Order Treasures:
10 6 15 3 8 20

This is perfect for scenarios when knights need to find the shortest path or explore the kingdom level by level!

Where to use (real life scenarios):

• Finding the shortest path in a network (breadth-first search).

• Social networks where you process connections level by level (e.g., friends of friends).

---

🖍Summary Drawing

---

🔮 What's Coming Next?

Our BST journey doesn’t stop here! In Part 4, things get even more exciting as we dig deeper into balancing and self-balancing trees. Ever wondered how to keep your tree lean and efficient? We’ll explore algorithms like AVL Trees and Red-Black Trees that keep your BST from getting too wild and unruly! 🧘‍♂️⚖️

Stay tuned—it’s going to be a fun and enlightening ride! 🚀

🔔 Don't forget to subscribe to my blog and YouTube channel to stay updated with all the latest content!