👋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.
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😇!