C++

How do you implement a Binary Tree in C++?

A binary tree in C++ is defined as a tree in which each node can have a maximum of two child nodes, i.e., left child node and right child node. There are different types of binary trees, such as full, complete, perfect, degenerate, etc. However, in this article, we will just be talking about the method of implementing a simple binary tree in C++ in Ubuntu 20.04.

Traversal of Binary Tree in C++:

A binary tree can be traversed in three different manners, i.e., pre-order traversal, in-order traversal, and post-order traversal. We will briefly be discussing all of these binary tree traversal techniques below:

Pre-Order Traversal:

The pre-order traversal technique in a binary tree is the one in which the root node is always visited first, followed by the left child node and then the right child node.

In-Order Traversal:

The in-order traversal technique in a binary tree is the one in which the left child node is always visited first, followed by the root node and then the right child node.

Post-Order Traversal:

The post-order traversal technique in a binary tree is the one in which the left child node is always visited first, followed by the right child node and then the root node.

Method of Implementing a Binary Tree in C++ in Ubuntu 20.04:

In this method, we are not only going to teach you the method of implementing a binary tree in C++ in Ubuntu 20.04, but we will also share how you can traverse this tree through the different traversal techniques that we have discussed above. We have created a “.cpp” file named “BinaryTree.cpp” that will contain the complete C++ code for binary tree implementation as well as its traversal. However, for the sake of convenience, we have broken down our whole code into different snippets so that we can easily explain it to you. The following five images will depict the various snippets of our C++ code. We will talk about all five of them in detail one by one.

In the first snippet shared in the image above, we have simply included the two required libraries, i.e., “stdlib.h” and “iostream” and the “std” namespace. After that, we have defined a structure “node” with the help of the “struct” keyword. Within this structure, we have first declared a variable named “data”. This variable will contain the data for each node of our binary tree. We have kept the data type of this variable as “char” which means that each node of our binary tree will contain character type data in it. Then, we have defined two pointers of node structure type within the “node” structure, i.e., “left” and “right” which will correspond to the left and right child of each node, respectively.

After that, we have the function for creating a new node within our binary tree with the “data” parameter. The data type of this parameter can either be “char” or “int”. This function will serve the purpose of insertion within the binary tree. In this function, we have first assigned the necessary space to our new node. Then, we have pointed “node->data” to the “data” passed to this node creation function. After doing that, we have pointed “node->left” and “node->right” to “NULL” since, at the time of the creation of a new node, both of its left and right children are null. Finally, we have returned the new node to this function.

Now, in the second snippet shown above, we have the function for pre-order traversal of our binary tree. We named this function “traversePreOrder” and passed it a node type parameter named “*temp”. Within this function, we have a condition that will check if the passed parameter is not null. Only then it will proceed further. Then, we want to print the value of “temp->data”. After that, we have called the same function again with the “temp->left” and “temp->right” parameters so that the left and right child nodes can also be traversed in pre-order.

In this third snippet shown above, we have the function for the in-order traversal of our binary tree. We named this function “traverseInOrder” and passed it a node type parameter named “*temp”. Within this function, we have a condition that will check if the passed parameter is not null. Only then it will proceed further. Then, we want to print the value of “temp->left”. After that, we have called the same function again with the “temp->data” and “temp->right” parameters so that the root node and the right child node can also be traversed in order.

In this fourth snippet shown above, we have the function for post-order traversal of our binary tree. We named this function “traversePostOrder” and passed it a node type parameter named “*temp”. Within this function, we have a condition that will check if the passed parameter is not null. Only then it will proceed further. Then, we want to print the value of “temp->left”. After that, we have called the same function again with the “temp->right” and “temp->data” parameters so that the right child node and the root node can also be traversed in post-order.

Finally, in the last code snippet shown above, we have our “main()” function that will be responsible for driving this whole program. In this function, we have created a pointer “*root” of “node” type and then passed the character ‘A’ to the “newNode” function so that this character can act as the root of our binary tree. Then, we have passed the character ‘B’ to the “newNode” function to make it act like the left child of our root node. After that, we have passed the character ‘C’ to the “newNode” function to make it act like the right child of our root node. Finally, we have passed the character ‘D’ to the “newNode” function to make it act like the left child of the left node of our binary tree.

Then, we have called the “traversePreOrder”, “traverseInOrder”, and “traversePostOrder” functions one by one with the help of our “root” object. Doing so will first print all the nodes of our binary tree in pre-order, then in-order, and finally, in post-order, respectively. Finally, we have the “return 0” statement since the return type of our “main()” function was “int”. You need to write all these snippets in the form of one single C++ program so that it can be executed successfully.

For compiling this C++ program, we will run the following command:

$ g++ BinaryTree.cpp –o BinaryTree

Then, we can execute this code with the command shown below:

$ ./BinaryTree

The output of all three of our binary tree traversal functions within our C++ code is shown in the following image:

Conclusion:

In this article, we explained to you the concept of a binary tree in C++ in Ubuntu 20.04. We discussed the different traversal techniques of a binary tree. Then, we shared with you an extensive C++ program that implemented a binary tree and discussed how it could be traversed using different traversal techniques. By taking help from this code, you can conveniently implement binary trees in C++ and traverse them according to your needs.

About the author

Aqsa Yasin

I am a self-motivated information technology professional with a passion for writing. I am a technical writer and love to write for all Linux flavors and Windows.