Elementary Data Structures with JavaScript - Binary trees - PART 1🚀
Tags: javascript, programming, codequality, webdev
Published: 2021-02-13 12:26:44

Table Of Contents
        * 🤓 [INTRODUCTION](#intro)
        * 📜 [DEFINITION](#define)
        * 👨🏻‍🔬[OPERATIONS](#operations)
        * 🏃🏻‍♀️[TRAVERSAL EXPLANATION](#traverse)
        * 🙏 [THANK YOU](#thank-you)


## 🤓 INTRODUCTION <a name="intro"></a>

Welcome, my dear hackers!🚀 Welcome to yet another blog article about elementary data structures. 

If you missed the previous article where we describe the Linked Lists and write pseudocode, you can check it out here:


{% link https://dev.to/codespresso/elementary-data-structures-with-javascript-linked-lists-part-2-1hbj %}

Today, we are going to start a **three-part article** about Binary Tree data structure. We will talk a bit about **theoretical stuff** because it will **make sense** of all the implementation that we will do using the JavaScript programming language. As you may know, data structures are not specific to any programming language, so you are free to use any other programming language of your choice.

Please feel free to connect with me via [Twitter](https://twitter.com/lazar_dev), [Instagram](https://www.instagram.com/codespressoweb/) or [LinkedIn](https://www.linkedin.com/in/lazar-stankovic-44a199177/)

Let's start our journey!
![journey](https://media.giphy.com/media/uAQm7xzHC0OB2VnSz4/giphy.gif)


## 📜 DEFINITION <a name="define"></a>

**Binary tree** is an ordered "tree" where each node has two "children" nodes at most.
- **Right child** and **Left child**

A subtree of some **node** N is called the left and right subtrees, and the node N is their parent. This is also known as the **Knut's binary tree**.

A **Strict binary tree** is a binary tree where each node has 0 or 2 subtrees.

**Complete binary tree** is a strict binary tree of a height **h** where all the **leaves** are at the level **h**.

A **Leaf** is a node that has no children nodes.

A total number of nodes in a **complete binary tree** of height h is:
- n=2<sup>h+1</sup> - 1

A **height** of a tree made up of **n** nodes is:
h = log<sub>2</sub>(n+1)-1

An **almost complete** binary tree is a tree where all of the levels, except the last one, filled out entirely.

A **balanced tree** is a tree where the height of the left and right subtree differs only by one.

## 👨🏻‍🔬 OPERATIONS <a name="operations"></a>

**Primitive operations**
- 📄 Get the content of the node N
- 👈🏻 Get the left child of the node N
- 👉🏻 Get the right child of the node N
- 👪Get the parent node of the node N
- 🧒🏻👶🏻 Get the sibling node of the node N
- ➡Check if the node N is a right child
- ⬅Check if the node N is a left child

**Composite operations**
- 🏃🏻‍♀️ Binary tree traversal
- 🌎Creating the binary tree
- 📥Insert into a binary tree
- ❌Delete a node from the binary tree
- 🔎Search an element in the binary tree
- 🔁Merging two binary trees


## 🏃🏻‍♀️ TRAVERSAL EXPLANATION <a name="traverse"></a>
There are a couple of ways to traverse a tree:

**PREORDER**
- Process the root node
- Traverse the left subtree
- Traverse the right subtree

**POSTORDER**
- Traverse the left subtree
- Traverse the right subtree
- Process the root node

**IN-ORDER**
- Traverse the left subtree
- Process the root node
- Traverse the right subtree

**BY LEVEL TRAVERSAL**
- Traverse all of the nodes by levels, starting from the node 0 a.k.a. the root node.

We will write minimal pseudocode for our traversal algorithms:

### PREORDER TRAVERSAL

```pseudocode
1 preOrder(root):
2    visit(root) //print out the content
3    preOrder(left(root))
4    preOrder(right(root))
5 exit procedure
```

### POSTORDER TRAVERSAL

```pseudocode
1 postOrder(root):
2    postOrder(left(root))
3    postOrder(right(root))
4    visit(root)
5 exit procedure
```


### IN-ORDER TRAVERSAL
```pseudocode
1 inOrder(root):
2    inOrder(left(root))
3    visit(root)
4    inOrder(right(root)) 
5 exit procedure  
```

### BY LEVEL TRAVERSAL
```pseudocode
//for this purpose we need to use the helper - the queue data //structure
1 levelOrderN(info, left_link, right_link, root)
2    pointer => root
3    while (pointer not equal to null)
4      visit(pointer)
5      //add all of the descendants into a FIFO queue
6      queue_enqueue(left(pointer))
7      queue_enqueue(right(pointer))
8      //read from a queue
9      pointer => queue_dequeue()
10     //if the queue is empty dequeue returns null
11   endwhile
12 exit procedure
```

# 🙏 THANK YOU FOR READING!<a name="thank-you"></a>
We are taking baby steps! The binary trees are a bit more complex data structure, so we would need to break this article in order for you (and me 😆) to not freak out. Stay tuned for the next chapter of this article!

References:
School notes...
School books...

Please leave a comment, tell me about you, about your work, comment your thoughts, connect with me! 

☕ SUPPORT ME AND KEEP ME FOCUSED!
<a href='https://ko-fi.com/Z8Z33D1HJ' target='_blank'><img height='36' style='border:0px;height:36px;' src='https://cdn.ko-fi.com/cdn/kofi4.png?v=2' border='0' alt='Buy Me a Coffee at ko-fi.com' /></a>

Have a nice time hacking! 😊