Binary search trees

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, 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 nodesthe 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++, and its meaning is the same as NULL. Both represent address 0.

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 << '
';    while (i < nodesNumber)    {        unsigned long long number; cout << "Value of node: "; cin >> number; cout << '
';        InsertNode(root, number);        ++i;    }    cout << "Binary search tree printed: "; Print(root);    cout << '
';    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

• Or you can find me on Linkedin

• Next topic: Intern reprezentation of primitive data types

• See you next time!