Implementing a Binary Tree

Creating a binary tree is simple once you understand the concept of a tree. The programming is similar to the way we created a linked list using a class and a structure. Since the program will be large we’ll break it down into smaller parts and discuss them separately.

First of all we need to define our node. The node of a tree is similar to a linked list node except that we will have two pointers in every node of the tree (for the linked list every node had just one pointer). So let’s create a structure to represent our node:

struct node
{
string data;
node *right;
node *left;
};

• We’ll create a binary tree to hold strings. So the data being held at each node will be of type ‘string’. You can use a character array or the pre-defined string class (I’m using the pre-defined string class, which is now available in all the latest compilers).
• Each node has to have a pointer to point to its right and left children. These pointers will have to be of type node itself.

node *root; This is the pointer which will point to the first node of our tree. It defines the starting memory location of our binary tree.

void destroy_tree(node*); We’ll need to destroy the tree (using the delete function) and this function will serve the purpose. We will call this function from the destructor of the tree class. The reason we make this private is because we don’t want to allow a user to access this function. This will be explained later.

The constructor: When a tree is created we don’t have any nodes in the tree. So the root pointer should point to NULL (otherwise it would be pointing to some unknown memory location).

Next we’ll need some member functions. The basic functions are:

• Adding a new node
• Destroying the tree

First let’s write the code for adding a new node to our tree:

Before starting with the code let’s write a pseudo algorithm (it is always a good practice to write algorithms before you jump into coding- it’ll save a lot of time).

1. Create a new node and assign the value to be stored to ‘data’.
2. Set the new node’s right and left pointers to NULL. Next we need to decide where to insert this node.
3. Check if root is NULL. If so then make the root point to this node (i.e. this will now become the first node of the tree).
4. Else compare the value of the node with the root node (the first node). If the value is less than the root node value then we’ll have to insert this node into the left side. Else it’ll have to go into the right side.
5. Let’s assume that our value is greater than the root node. So, we’ll have to insert it to the right of the root node. Check if the right pointer of the root node is NULL. If so then we can simply make the right pointer point to our new node. If it is not NULL it means that some node is already present to the right of the root node. So compare the value with the existing node value and repeat the above steps (steps 3, 4 and 5) till you find a vacant place to insert the node.

You must have guessed by now that we’ll need an iterative loop to insert the new node.

void tree::addnode(string str)
{
	node *newnode,*ptr;	//Creating a new node
	newnode=new node;
	newnode->data=str;
	newnode->left=NULL;
	newnode->right=NULL;

	if (root==NULL)		//Determining the position to insert the new node
	{
		root=newnode;
	}
	else
	{
		ptr=root;
		while (ptr!=NULL)
		{
			if (newnode->data < ptr->data)
			{
				if (ptr->left==NULL)
				{
					ptr->left=newnode;
					ptr=NULL;
				}
				else
				{
					ptr=ptr->left;
				}
			}
			else
			{
				if (ptr->right==NULL)
				{

					ptr->right=newnode;
					ptr=NULL;
				}
				else
				{
					ptr=ptr->right;
				}
			}
		}
	}
}

The code might seem complicated but it’s actually easy if you’ve understood the algorithm for inserting a new node.

Remember: Inserting a new node means that all we need to do is make the pointers point to the correct addresses.

The destructor

In our destructor we pass the root pointer as argument to the destroy_tree( ) function (because we want to destroy all the nodes from the root onwards). The algorithm to destroy a tree is as follows:

• We cannot destroy from top to bottom (i.e. you can’t first delete the root node, then the children and so on).
• Check if the root node has a left child. If it does then destroy that left child. Before destroying the left child we need to check whether that node has a left child of its own. If it doesn’t then check whether it has a right child. If it doesn’t then we can delete the node else we need to go right down to the bottom of the tree to locate the node with no children. From that node onwards we have to delete and approach the top of the tree.

The algorithm may seem a little complex to implement at first sight. But if you analyze the procedure carefully then you’ll find a recurring pattern. Recursion would help us to solve this problem easily. The code will be:

We just keep on recursively calling the same destroy function. Take an example and think like the compiler to understand the logic.

As expected, the child node (srinath) is deleted first before the root node is deleted.

Remember: The tree structure is decided based on the way we store values in the tree. In the above example, if srinath were inserted first into the tree then michael would have been inserted to the left of srinath.