Tree

Tree: is a Non-linear Data structure

-Linear vs Non-Linear DS :

-What is a Tree?

-Tree Definitions :

-Tree Implementation :

-Breadth First Traversal : or level by level

-Breadth First Traversal or Breadth First Search BFS

Started from the root. Then print each level

Get Emad Mohamed’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

So output : 0 1 2 3 4 5 6

Breadth First Traversal pseudo code :

Here we will use the queue

Example :

Dequeue(0) then push to queue the children of 0 = 1 2 3

Dequeue(1) then push to queue the children of 1 = 4 5

In the final, we get :

JS code that explains BFS :

// 1. Definition of a Tree Node
class Node {
    constructor(value) {
        this.value = value;
        this.left = null;   // Left child
        this.right = null;  // Right child
    }
}

// 2. The BFS Function (Using a Queue)
function breadthFirstSearch(root) {
    // Base Case: If the tree is empty, just stop
    if (root === null) return;

    // Step A: Initialize an empty queue and add the root node
    const queue = [];
    queue.push(root);

    // Step B: Loop as long as the queue is not empty
    while (queue.length > 0) {
        // 1. Remove the front node from the queue to process it
        const currentNode = queue.shift(); 
        console.log(`Visited Node: ${currentNode.value}`);

        // 2. If the current node has a left child, push it to the queue
        if (currentNode.left !== null) {
            queue.push(currentNode.left);
        }

        // 3. If the current node has a right child, push it to the queue
        if (currentNode.right !== null) {
            queue.push(currentNode.right);
        }
    }
}

// --- Testing the BFS Algorithm ---

// 3. Building the exact same Binary Tree
//        1
//       / \
//      2   3
//     / \
//    4   5

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

// 4. Run BFS
console.log("--- Starting BFS Traversal ---");
breadthFirstSearch(root);
console.log("------------------------------");

output :

--- Starting BFS Traversal ---
Visited Node: 1
Visited Node: 2
Visited Node: 3
Visited Node: 4
Visited Node: 5
------------------------------