Hi folks, in this article we will talk about the term "Binary Tree"

In addition, we'll implement a Breadth First Search (BFS) algorithm.

This is the first algorithm we perform on the Binary Tree.

It's also a very popular algorithm you MUST know for the DSA interview.

What's a Tree?

is a Collection of Nodes and Edges WHERE

👉 There is ONERoot node

👉 There is ONLY ONE UNIQUE path between any two nodes.

👉 Nodes have relationships with the others.

Here's an example of a Tree:

Image Source: TutorialPoint

We can make a few statements from the above images:

👉 A is the root node. (has NO parent)

👉 A has two children

👉 B and C have the parent of A

👉 B and C are siblings

👉 C has two children.

Another Image of Tree:

Here are someterminologies about Trees.

Leaf Node

👉 We have H, I, J, F,and G are all leaf node because they have 0 children.

Level

👉 Node A is on the level 0

👉 We can say B and C are on the same level 1

👉 We can assign a number to each levels.

Height

When we refer to the tree's height, we're REALLY referring to the LARGEST LEVEL.

In the Tree above, the height is 3.

Simply because 3 is the largest level number.

NOT a Tree - Examples

There's a ROOT node - the X

BUT, there is MORE THAN ONE WAYS to go from X to Z

X => Z
X => Y => Z

Next,

In this example, we have one Root node P - valid the first requirement of a Tree.

BUT,

We don't have a UNIQUE path fromQ to S

There's an infinite cycle from Q to S

We often used the Tree Data Structure to represent a Hierarchy.

For example: A company Hierarchy, or Folder and Files system in the computer...

What's a BINARY Tree?

👉 It's definitely a TYPE of Tree.

👉 BUT, Binary Tree is the special tree, where EACH node has AT MOST TWO CHILDREN.

While a General Tree a node can have MORE than 2 children.

Image Source: CoderByte

Implement a Binary Tree

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

  const a = new Node('a');
  const b = new Node('b');
  const c = new Node('c');
  const d = new Node('d');
  const e = new Node('e');
  const f = new Node('f');
  const g = new Node('g');

  a.left = b;
  a.right = c;
  b.left = d;
  b.right = e;
  c.right = f;

Here is the Binary Tree we just build

Breadth-First Traversal

▶ Is the way we can access every value of every node of a Binary Tree in a particular order.

▶ The term Breadth-First refers to the width of the tree. We flow across from Left to Right on each level of our Tree.

▶ We focus on visiting all the nodes on one level before moving on to the next level.

Back to the example, as a result of doing BFS Traversal, we will end up with the result look something like this: a, b, c, d, e, f

Implement BFS

Require us to have a basic understanding of Queue Data Structure. (FIFO)

Queue is the Data Structure that allows us to remove elements from both the head and the tail (front or back) in constant time O(1)

I will talk more about this data structure in my future articles.

To implement this algorithm, we will take the iterative approach rather than recursive.

This is because of the recursive approach can be way more challenging.

Here is the code

const breathFirstPrint = (root) => {
    const q = [ root ];

    while (q.length) {
       const current = q.shift();
       console.log(current.value);
       if (current.left) q.push(current.left);
       if (current.right) q.push(current.right);
    }
};

breathFirstPrint(a);
// Result: a b c d e f

Complexity Analysist:

Time: O(n) - we have to visit every node in the Tree.

We know exactly that over time we'll have n iteration.

Because every node of the Tree leaves the Queue exactly ONE.

Space: O(n) - we have to keep track of every node in the queue - it takes linear space.

Applying BFS to solve some problems

Search for a target number in Binary Tree

Write a function bfs(root, target) takes in the root of a binary tree and a target value as an arguments.

The function should return a boolean indicating whether or not the tree contains the target value.

Solution:

const bfs = (root, target) => {
    const q = [ root ];

    while (q.length) {
       const current = q.shift();
       if (current.value === target) return true; 

       if (current.left) q.push(current.left);
       if (current.right) q.push(current.right);
    };

    return false;
};

bfs(a, 'e'); // TRUE
bfs(a, 'z') // FALSE

Calculate Sum of a Tree

Write a function sumTree(root) takes in the root of a binary tree as an argument.

The function should return the total sum of all values in the tree.

You can assume that the Tree only contains number values.

const a = new Node(3);
const b = new Node(2);
const c = new Node(7);
const d = new Node(4);
const e = new Node(-2);
const f = new Node(5);

 a.left = b;
 a.right = c;
 b.left = d;
 b.right = e;
 c.right = f;

const bfs = (root, target) => {
    const q = [ root ];
    let sum = 0;

    while (q.length) {
       const current = q.shift();
       sum += current.value;

       if (current.left) q.push(current.left);
       if (current.right) q.push(current.right);
    };

    return sum;
};

sumTree(a) // 19

Binary Trees & Breadth First Search