by A tree is a data structure similar to Linked list in which each node points to multiple nodes instead of simply pointing to the next node. A tree is called Binary tree if each node in a tree has maximum of two nodes.
An empty tree is also a Binary tree. We can call the two children of each node as Left and Right child of a node. The node of the tree which has no parent is called the Root of the tree. Perhaps Binary tree is the most used tree data structure in the programming world. Before going ahead have a look into Binary Tree basics.
Binary Tree Implementation
Here we are going to talk about a very simple implementation of Binary tree using Linked List similar data structure. Also we will discuss about some of the basic operations that are possible in Binary Tree such as:
- Inserting an element in Binary Tree
- Deleting an element in Binary Tree
- Traversing an element in Binary Tree
- Searching an element in Binary Tree
Let’s have a look into basic C++ class definition for Binary Tree.
class BinaryTree
{
public:
int m_data;
BinaryTree* m_left;
BinaryTree* m_right;
BinaryTree (int data);
BinaryTree (int data, BinaryTree* left, BinaryTree* right);
};
Binary Tree Class Function Implementation
Let’s have a look into all the functions/operations definition of Binary Tree Class.
Constructor/Destructor implementation
/* This constructor will be called when an isolated node is created */
BinaryTree::BinaryTree (int data): m_data(data),
m_left(NULL),
m_right(NULL)
{}
/* This constructor will be called when we want to set left and right child along with node creation */
BinaryTree::BinaryTree (int data, BinaryTree* left, BinaryTree* right): m_data (data),
m_left (left),
m_right (right)
{}
/* No dynamic allocation is being done, hence nothing to delete here */
BinaryTree::~BinaryTree ()
{}
Searching an element in Binary Tree
This operation will search an entry in the Binary Tree and it will return the node if it is found or NULL pointer will be returned.
Let’s look into the sample code.
BinaryTree* search_node_in_binary_tree (BinaryTree* root, int searchData)
{
if (!root)
{
return NULL;
}
if (root -> m_data == searchData)
return root;
else
{
BinaryTree* temp = search_node_in_binary_tree (root -> m_left, searchData);
if (temp)
return temp;
return search_node_in_binary_tree (root -> m_right, searchData);
}
}
Inserting an element in Binary Tree
This operation will add an entry into the Binary tree. There are two versions can be possible for inserting a node into binary tree.
Inserting an element in Binary Tree at first available place
This operation will add an entry into the Binary tree at the first available place.
Let’s look into the sample code.
bool insert_at_first_available_place (BinaryTree* parent, BinaryTree* newNode)
{
if (!parent)
return false;
if (!parent -> m_left)
{
parent -> m_left = newNode;
return true;
}
else if (!parent -> m_right)
{
parent -> m_right = newNode;
return true;
}
else
{
if(!insert_at_first_available_place (parent -> m_left, newNode))
{
return insert_at_first_available_place (parent -> m_right, newNode);
}
return true;
}
}
Inserting an element in Binary tree as a child of parent node
This operation will add an entry into the Binary tree as a child of parent node. If the parent node already has both children then new node will be added as a grandchild of the parent node.
If parent node is not present in Binary tree then new node will be added at the first available place as above mentioned method.
Let’s look into the sample code.
/* New node will be added as a child/grandchild of the searched node.
* If searched node is not found then first available node will be found
* from root and new node will be placed there */
void insert_after_certain_element (BinaryTree* root, int newData, int searchData)
{
BinaryTree* temp = new BinaryTree (newData);
if (!root)
{
cout << "Empty Binary Tree, Adding new node as Root node" << endl;
}
BinaryTree* searched_node = search_node_in_binary_tree (root, searchData);
if (!searched_node)
{
searched_node = root;
}
if (!insert_at_first_available_place (searched_node, temp))
{
cout << "Inserting new element in Binary Tree failed !!!" << endl;
}
}
Traversing all nodes in Binary Tree
Traversing nodes in a Binary Tree is actually a very big topic which we will discuss in detail in its own article. Here we are going to provide a simple method to visit all nodes present in a Binary Tree.
Let’s look into the sample code.
void print_binary_tree (BinaryTree* root)
{
cout << " " << root -> m_data;
if (root -> m_left)
print_binary_tree (root -> m_left);
if (root -> m_right)
print_binary_tree (root -> m_right);
}
Deleting a node in Binary Tree
Deleting a node in Binary Tree is quite a big task and to avoid becoming this article quite lengthy, we will discuss deletion of a node in Binary tree in it’s own article.
Let’s look into the sample main function which utilizes Stack class definition and functions defined above.
void print_tree (BinaryTree* root)
{
cout << "Binary tree contents: ";
print_binary_tree (root);
cout << endl;
}
int main ()
{
BinaryTree* root = new BinaryTree(20);
insert_after_certain_element (root, 10, 20);
insert_after_certain_element (root, 30, 20);
insert_after_certain_element (root, 40, 20);
insert_after_certain_element (root, 1, 40);
insert_after_certain_element (root, 50, 30);
insert_after_certain_element (root, 60, 20);
print_tree (root);
if (search_node_in_binary_tree (root, 1))
{
cout << "Searched data: 1 found in binary tree" << endl;
}
else
{
cout << "Searched data: 1 not found" << endl;
}
}
Let’s analyze the output of this main function.
Binary tree contents: 20 10 40 1 60 30 50
Searched data: 1 found in binary tree
