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 from**`Q`

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 leve**l.

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