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

**data type as having three attributes: an unsigned long long variable -**

`Node`

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

**variable and insert it. If the**

`Node`

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

**variables and we made sure that we could insert them correctly. Now we need to think about how we can**

`Node`

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

## Top comments (2)

NULL and nullptr aren't same. NULL can be overloaded as int data type in c++

I think that the part with NULL and nullptr was written ambiguously. I will consider rewriting it. Thank you😇!