Tree

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

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
------------------------------