This article is about Programming
Implementing a Binary Tree in C++
By NIIT Editorial
Published on 20/08/2021
A binary tree is one of the most extensively used tree data structures. It is a hierarchical data structure wherein each node has two children, the left child and the right child. A typical binary tree consists of the following components:
Ø A root node
Ø A left subtree
Ø A right subtree
Binary Tree representation:
1. Sequential representation:
Above is a pictorial representation of a binary tree. This particular representation requires an array structure to implement the tree. The size of an array is equal to the number of total nodes in the tree. The root node's index is 0. For example- if a node is at “i” location, then its left child is at the ‘2i’ index, and the right child is at the ‘2i+1’ location in the array. The visual representation of the array is given below:
2. Linked-list Representation:
In this, a linked list is used to store the nodes of the tree. Various nodes are scattered in the memory in non-contiguous locations, and those nodes are connected using the parent-child relationship as signified in a tree.
As we can see, the topmost node ‘A’ is the parent node of ‘B’ and ‘C’. Each node contains a pointer to the left subtree and a pointer to the right subtree in the above representation. Thus, node A has a pointer corresponding to the right child node ‘C’ and a pointer to the left child node ‘B’. The box in the middle represents the data in the node. The nodes that don’t have a child are known as ‘ass leaf’ nodes. They do not have a pointer to their subtrees and which is why they are set to NULL.
To implement a binary tree, it is necessary to define the conditions for new data to enter into the tree.
Binary tree implementation in C++
Now, we will create a binary tree programme using linked list representation in C++.
In the fragment below, we have used a class to declare a single node and used it to declare a linked list of nodes.
If you want to declare a group of data whether of similar or different data types, it is declared using the 'class' keyword. In the above fragment, the class is "BT" and it contains a pointer to left and pointer to right. The “BT *lChild” is pointer to node and it stores the address of left child and similarly “BT *rChild” is a pointer for right. The “int” data declares data of int type.
In linked list representation, the information of the address of the head node is kept. All the other information can be accessed using this head node. In the given instance, the address of the root node is known. This is mandatory as without knowing the address of the head node, we won’t be able to access the tree using links.
In order to declare the tree, we will first need to create a pointer to the node that will store address of root node by: BT* root. Since our tree does not have any data yet, we will assign our root node as NULL. BT* root = NULL.
In the above image, we have assigned the left and right cells of nodes as addresses to their children. The middle cell is for data. The identity of the tree is the address of the root node and we have designated a pointer to the node in which we are storing the address of the root node.
For an empty tree, the root pointer should be set as NULL. Let’s suppose this ‘rootPtr’ to be a different box pointing towards different nodes in our tree, and for pointing to different nodes we have to pass the address of the nodes. At the beginning, it is not pointing towards any node and therefore we will put NULL value.
Since now our tree is empty, let’s insert new data into our tree. To do so, we will have to call and define the ‘insert’ function.
In the fragment given below, we will define Insert function which is taking 2 arguments as "root" and new integer data to be inserted in our tree as follows:
In the above fragment, ‘else if’ condition is done when the root pointer is not NULL. When the new data is less than the data present in the root node, then that data is inserted into its left pointer corresponding to the left child node and assigned that node's parent as root node. Likewise, if the new data is greater than data of root node, then insert that integer into its right child and assign its parent as root node. In the above fragment, root->left is the pointer to its left node. The insert function will call itself again. It’ll check if the root is empty and then follow the same procedure. This is called a recursive loop. The following is a recursive loop code:// Function to create a new Node
Operations on Binary tree
After successfully creating a new binary search tree, we will now traverse the tree PREorder. A function called printInOrder will be implemented which will traverse the tree from its root nude, then its left subtree and then its right subtree.
1. Pre order Traversal
In this example, preorder(Root, Left, Right) : 1 2 3 4 5
The algorithm for traversing preorder is : using recursion.
The procedure as follows:
1. Go to the root
2. Then traverse the left subtree, call preorder(left-subtree)
3. Then traverse the right subtree, call preorder(right-subtree).
The preorder function is defined as follows:-
2. How to search a key in the Tree
Now, find out if the key exists in our tree or not. To do so, we need to compare the key with the current node. If the key is less than the current node, the left subtree needs to be searched, or else the right subtree would be searched. Till the time key is not found, compare it with the current node. This process is known as a recursive function.
3. How to find minimum and maximum values in Binary Tree
The easiest thing to find in the binary search tree is finding the minimum and maximum values. We have to get to the leftmost value to get the minimum value. However, to get the maximum value, we have to get to the rightmost value given in the binary tree.
4. Deleting or removing a node from the tree
Below mentioned are the three cases with which the node from the tree can be removed:
One of the easiest cases is to remove the leaf node. Only the node that doesn’t have a child needs to be removed. 8, 12, 17, and 25 are the leaf nodes in our tree.
If the removed node has one child (right or left), then the parent code's address needs to be pointed out to the child node of the deleted ones. For example, in the above tree, there are two single nodes, 3 and 88. We have to point to the parent code of 53 to 31 if we want to remove node 88. Thus, make the right node of 31 as 53.
Removing the two children nodes. If the node has two children, you need to find out the predecessor or successor of that particular node first and replace it with the same. For example, If you want to remove node 12, the predecessor needs to be removed 7. Now, 7 will come in place of 12. 7 has two children, i.e. 3 and 15. As we can choose only one (either successor or predecessor), there can be two possible binary representations after deleting a node.
In such cases, the successor and predecessor of a node need to be defined first.
4.1 Finding the successor of the key
The immediate number after a key is referred to as the successor. If we wish to identify the successor of a specific key, say "T," we'll look for the minimum key in the right subtree of T. Our bare-bones feature could come in handy here. The minimal key will be found in the right subtree of T.
4.2 Finding T’s predecessor
The key that comes just before T is Predecessor. We'll make use of the maximum function we've already defined. Now we need to find the maximum value, which is the left subtree of T.
Removing a key from Tree
There are three ways in which a node can be removed:
Remove a node that has no child i.e. a node with node->lChild = NULL and node ->rChild = NULL.
Remove nodes having only one child (left or right).
node->lChild == NULL && node->rChild != NULL
node->lChild != NULL && node->rChild == NULL
We must delete the node and reconnect the child node to the removed node's parent node.
- Delete a node with two children. We might use the successor or predecessor of the target node to replace it. For example, if the target node to be removed is 12 and has two children, we have two choices: replace 12 with its predecessor (7) or replace 12 with its successor (8). (15). Below mentioned is the code that can be taken into consideration for the three cases.
So with this, we come to an end of the article. You must have got the complete understanding of how to create a Binary Tree in C++. To get a better insight into C++ you can choose PGP in Full Stack Product Engineering by NIIT and add it to your skills.
PGP in Full Stack Product Engineering
Become an Industry-Ready StackRoute Certified Full Stack Product Engineer who can take up Product Development and Digital Transformation projects. Job Assured Program* with a minimum CTC of ₹7LPA*
Job Assured Program*
Easy Financing Options