Binary search trees🌳
Tags: programming, tutorial, cpp, beginners
Published: 2022-07-24 13:35:00

## 👋Heeelloo everybody! 🔥🚀

` `
-> This post is about **binary search trees**🌳. They are represented by **nodes linked together** to simulate a hierarchy, and these nodes are positioned **following a rule**. 

-> I will walk you through the implementation of a binary search tree. Working with trees **requires knowledge about pointers**, **the memory layout of a C program**, **memory allocation**, **and a good understanding of recursion**. 

-> We focus on binary search tree🌳 because this is a **time-efficient** data structure. We call it **binary** because every node **can have at most two children**. It is a **search tree** because it **respects a particular condition** which says that **every node with a value smaller than the root node is going to be placed on the left of the root node, and every node with a value bigger than the root node is going to be placed in the right of the root node**. This rule is applied recursively for every right subtree and left subtree.

-> **Searching**, **accessing**, **inserting**, and **deleting** in a binary search tree🌳 are **usually** done in **O(log n)**. But there is a chance that a binary search tree can have a structure **similar to a linked list**, and the operations mentioned above will be done in **O(n)**. This situation is a drawback for the tree data structure and it happens when every new node has either a **smaller** value than the last node, or a **bigger** value  than the last node. Try to draw a binary search tree with these values: `10, 9, 8, 7, 6, 5, 4` and with these values: `4, 5, 6, 7, 8, 9, 10` and see what happens.

-> Happily, another tree🌳 data structure, **AVL**, is an improvement of classical trees. **AVL** is a **self-balancing** tree, and by balancing, we avoid the situation when the tree can become a linked list. But this is another discussion.

-> We can implement trees with more than two children, **but time complexity will not change**. Only the logarithm base will change, but **it doesn't matter in complexities**, so again, the time complexity will be **O(log n**) in the best case and **O(n)** in the worst case.

` `
## 1. First step: creating a `Node` data type

**To work with a tree data structure**, we need to **create a new data type**, a **`Node`** data type. Trees🌳 use nodes. Here we define our **`Node`** data type as having three attributes: an unsigned long long variable - **representing the information to be stored**(also it can be any primitive or abstract data type. I used a primitive data type for simplicity), **a reference to the left child**, and **a reference to the right child**.

```

struct Node
{
    unsigned long long data;
    Node* left;
    Node* right;
};

```

` `
## 2. Second step: generating `Node` variables

After we define how a **`Node`** data type looks, we **need to be able to create variables of that type**. We are working with heap memory, so we must **dynamically allocate memory** for our new nodes—the **new** operator requests memory **of the size of our data type**. Then we initialize data attribute and references. The **nullptr** keyword was introduced in C++, representing 0 as an adress and only as an adress; **nullptr** is a keyword with pointer type. On the other hand, **NULL** is by default 0 and is not always a pointer. I will post about the difference between `nullptr` and `NULL` in the future. Because we are working with pointers and we are in C++, is better to use **nullptr**.
```

Node* CreateNode(unsigned long long Data)
{
    Node* newNode = new Node;

    newNode->data = Data;
    newNode->left = nullptr;
    newNode->right = nullptr;

    return newNode;
}

```

` `
## 3. Third step: inserting nodes

After we defined how our **`Node`** data type looks and we made sure that we can create variables of that type, we need to be able to **put these variables in such a way that respects the definition of a binary search tree**. We will create a function for inserting in a binary search tree. I prefer the recursive method as it is shorter. We need **two arguments** for that function: **the root node** and **the information/object to be stored**. If the root is null, then we know that it is time to create a new **`Node`**  variable and insert it. If the **value** of information/object is **greater** than the **value** of the **actual root node**, then we go to the **right**; if not, then we go to the **left**. 

```

void InsertNode(Node*& Root, unsigned long long Data)
{
    if (Root == nullptr) Root = CreateNode(Data);
    else if (Data > Root->data) InsertNode(Root->right, Data);
    else InsertNode(Root->left, Data);
}

```

` `
## 4. Fourth step: printing a binary search tree

We created a **`Node`** data type, and we made sure that we could generate **`Node`** variables and we made sure that we could insert them correctly. Now we need to think about how we can **see** our data structure. For this, we need to use **algorithms for depth traversals or breadth traversal**. There are four possible algorithms: **inorder**, **preorder**, **postorder** and **level order traversal**. I use preorder for this example.

```

void Print(Node* Root)
{
    if (Root)
    {
        cout << Root->data << ' ';
        Print(Root->left);
        Print(Root->right);
    }
}

```

` `
We are done. We have all pieces for working with a binary search tree. 
Here is the complete code🔥:

```

#include <iostream>
using namespace std;


struct Node
{
    unsigned long long data;
    Node* left;
    Node* right;
};


Node* CreateNode(unsigned long long Data)
{
    Node* newNode = new Node;

    newNode->data = Data;
    newNode->left = nullptr;
    newNode->right = nullptr;

    return newNode;
}


void InsertNode(Node*& Root, unsigned long long Data)
{
    if (Root == nullptr) Root = CreateNode(Data);
    else if (Data > Root->data) InsertNode(Root->right, Data);
    else InsertNode(Root->left, Data);
}


void Print(Node* Root)
{
    if (Root)
    {
        cout << Root->data << ' ';
        Print(Root->left);
        Print(Root->right);
    }
}


int main()
{
    Node* root = nullptr;
    unsigned long long i = 0, nodesNumber;
    cout << "Number of nodes to be added: "; cin >> nodesNumber; cout << '\n';

    while (i < nodesNumber)
    {
        unsigned long long number; cout << "Value of node: "; cin >> number; cout << '\n';
        InsertNode(root, number);
        ++i;
    }

    cout << "Binary search tree printed: "; Print(root);
    cout << '\n';

    return 0;
}

```
This is a basic structure. I wanted to give you the **main idea**. We can also create a **Tree**🌳 data type and think about **Tree**🌳 as an object with attributes rather than a simple variable called root. But from here, you can improve/change this implementation as you like. Feel free to explore.🗺️ and be curious.

` `
❗Observations:
- I focused on the idea rather than on a real-world scenario where I must consider validations and other stuff. 

- I have used **C++** programming language.

` `
- Emanuel Rusu👨‍🎓

- You can visit my [GitHub](https://github.com/Emanuel181)

- Or you can find me on [Linkedin] (https://ro.linkedin.com/in/emanuel1)
              

- Next topic: **Intern reprezentation of primitive data types**

- See you next time! 👋