How it works... – binary tree

We created a structure called tree consisting of the following members:

Internally, the tree will be maintained through an array; an integer array is defined of the size 20. For our purposes, let's assume that the user doesn't enter more than 20 elements for the tree. However, you can always increase the size of the macro to any larger number you desired.

The user is prompted to specify the number of elements they want to enter for the tree. Let's say the user wants to enter seven elements for the tree; here, the value 7 will be assigned to the len variable. The user is prompted to enter the seven integers and the values entered by them will be assigned to the arr array, as shown in the following screenshot:

The build function is invoked and the array, arr, containing the tree elements and the length of the array, len, are passed to it. In the build function, we need to create a root node of the tree. To create a root node of the tree, the makeroot function is invoked and the first element of the array, arr, is passed to it as an argument. In the makeroot function, a node called rootNode is created and the value of the first array element is assigned to its data member. Because the root node of the tree is not pointing at any other node at the moment, the right and left child of the root node are set to NULL:

The makeroot function ends and rootNode is returned to the build function. In the build function, a temp pointer is set to point at rootNode. All of the array elements from index 1 and above are compared with the data members of the temp node, that is, the root node. If the array element is smaller than the data member of the temp node, the array element will be added as the left child of the root node. Also, if the array element is larger than the data member of the temp node, it will be added as the right child of the root node, for example, if the second array element is 20 and the root node is 40. Because 20 is smaller than 40, it is checked whether the left pointer of the temp node is NULL. Because the left pointer of temp is NULL, the leftchild function is invoked and 20 is passed to it. In the leftchild function, a new node is created called newNode. Here, the second array element (20) is assigned to the data member of newNode. The left and right pointers of newNode are set to NULL. The left pointer of temp is set to point at newNode, as follows:

Control goes back to the build function, where the for loop will pick up the next array element for building the tree. Let's say the next array element is 60. Again, a temp pointer is set to point at the root node. The value 60 is compared with the root node, which is 40. Because the value of the array element, 60, is greater than the root node, 40, the right child of the root node is checked. Because the right child of the root node is NULL, the rightchild function is invoked and the temp pointer and the array element, 60, are passed to it. In the rightchild function, a new node is created called newNode and the value 60 is passed to it, which is assigned to its data member. The left and right pointers of newNode are set to NULL. The right pointer of rootNode is set to point at newNode, as follows:

After completing the rightchild function, control goes back to the build function, where the for loop picks up the next array element for building the tree. The next array element is 80. A temporary pointer, temp, is set to point at the root node. The root node, 40 is compared with the new element to be added, 80. Because 80 > 40, the right child of the temp node is checked. The right pointer of the temp node is not NULL, so the temp pointer is set to point at its right node, as follows:

Now, the right pointer of temp is checked again. This procedure is repeated until the right pointer of temp is found to be NULL. The right pointer of 60 is NULL, so the rightchild function is invoked and temp, 60, and the new element, 80, are passed to it. In the rightchild function, a new node is created called newNode and the value 80 is assigned to it. The right and left pointers of newNode are set to NULL. The right pointer of temp is set to point at newNode, as follows:

After completing the rightchild function, control jumps back to the build function, where the for loop picks up the next array element for building the tree. After all of the array elements have been used, the binary search tree will look as follows:

Once the binary search tree has been created, the travino function is invoked for inorder traversal of the binary tree and the root node is passed to it.