# Sorting a Binary Tree

I have written a simple binary tree using structures and a couple of functions in order to add, search, find the minimum and maximum values, remove a node as well as destroy the node, the problem is that I have been using recursion and dealing with it in the same way and I am having a hard time trying to comprehend if my function for sorting the algorithm is efficient enough.

The whole code is:

#include<iostream>
using namespace std;

/*
This is a very simple example demonstrating a very basic binary tree to be
implemented using structurs, later on I would like to create this by using
classes, but for now, structures and pointers would suffice
*/

/*
* The node is created in here, notice how the pointer has the ability to
* self reference to 2 different positions, this means that there is the ability
* to store to 2 different branches of memory
*
*/

struct node{
int key_value;
node * p_left;
node * p_right;
};

/*
*
*
*/

node* add(node * p_tree, int key) {
//--The base case of the recursive function will be placed in here
//--since binary trees are recursive in nature and linked data structures
//--are as a whole in terms of space and memory, the recursive function will
//--suffice for most cases involving binary trees.
//--In this case, if the given parameter is null, we create the tree
//--by allocating the necessary memory space
if (p_tree == NULL) {
node * pnew_tree = new node;
pnew_tree->p_left = NULL;
pnew_tree->p_right = NULL;
pnew_tree->key_value = key;
return pnew_tree;
}// end of base case

//--Depending of the value of the node, we determine if we will add to the left side or the right side of the subtree
if (key < p_tree->key_value){
// if it is less than the value, we add to the left
}
else{
}
return p_tree;
} // end of function

/*
*
* This is where the search function will be created
* in here the function will go over all the subtrees untill the one with the necessary key is returned
* again, this uses recursive functions doing things step by step:
*
* First: Look to see if the given tree node is empty(NULL) if yes then return NULL
*
* Second: If we find the key by referencing the key value, then we are done and return that particular tree
*
* Third: Otherwise, look into the left and right sides of the tree making recursive calls to this very same function until
*        the one that we are looking for is found.
*
*/

node* search(node *p_tree, int key) {
//--First:
if (p_tree == NULL) { return NULL; }

//--Second:
else if (p_tree->key_value == key) { return p_tree; }

//--Third:
else if(key < p_tree->key_value) {
search(p_tree->p_left, key); //--Thus it looks into the left with the same recursive algorithm
}
else {
search(p_tree->p_right, key);
}
}//--End of recursive search function

/*
*
* Easiest function to implement, since the delete key is used being that the whole concept falls inside memory being allocated to the
* list via the creation of new nodes(this means using the new keyword to allocate memory, much like creating new objects in other languages)
*
* First: Check to see if passed tree is not null, if not null destroy the left and right subtree using the same function
*        else nothing.
*
* NOTE: The return value is set to void since it returns nothing back to the list
*
*/
void destroy_node(node* p_tree) {
//--First
if (p_tree != NULL) {
destroy_node(p_tree->p_left);
destroy_node(p_tree->p_right);
cout << endl;
cout << "Destroying left subtree node" << endl;
cout << "Destroying right subtree node" << endl;
cout << "Deleting the entire node: " << p_tree->key_value << endl;
cout << endl;
delete p_tree;
}
}//--End of recursive destroy function

/*
*
* Finding the max value is simple, we evaluate the left and right node and use base cases to see which node to return
* Why just right?
* looking back at the theory behind binary trees, the tree on the right is always the biggest element. That is how trees are normally sorted.
* there is no need to look at the keys, the code will sort out by itself in this space since if it is not null it will return the highest.
*/
node* return_max(node* p_tree) {
if (p_tree == NULL) {
return NULL;
}
if (p_tree->p_right == NULL) {
return p_tree;
}
return return_max(p_tree->p_right);
} //--End of return max recursive function

/*
*
* Max node, basically the opposite of the avobe taking advantage of the fact that the left node is lesser
* recursion will be used again
*
*/

node* return_min(node* p_tree){
if (p_tree == NULL) {
return NULL;
}
if(p_tree->p_left == NULL) {
return p_tree;
}
return return_min(p_tree->p_left);
}//--End of recursive return min function

/*
*
* We need a remove max function in order to properly remove the biggest node in case it is found, that way we can implement a recursive
* algorithm inside the  function in charge of removing the node we want, we can simply remove the node by using delete or destroy once we
* find it because that would only destroy the entire tree! No no, that is not good.
*
*/
node* remove_max_node(node* p_tree, node* p_max_node) {
if (p_tree == NULL) { return NULL;}

if (p_tree == p_max_node) {
return p_max_node->p_left; //--Because the left one is lesser
}
//--Now for the recursive call, implementing this means that we will remove from the node on the right
//--basing us on the sense that the right tree is the highest one, it will go then from top to bottom
p_tree->p_right = remove_max_node(p_tree->p_right, p_max_node);
//--return the tree after the changes in the addresses have been conducted properly
return p_tree;

}

/*
*
*
*
*
* Removing from a tree is also simple based on the recursive nature of the element being discussed
*
* First: Check to see if the tree is null, if yess, return null
*
*/
node* removeN(node* p_tree, int key) {
//--First:
if (p_tree == NULL) { return NULL;}
//--Second
if(p_tree->key_value == key) {
//--Third:
if (p_tree->p_left == NULL) {
node* p_right_sub = p_tree->p_right;
delete p_tree;
return p_right_sub;
}
if (p_tree->p_right == NULL) {
node* p_left_sub = p_tree->p_left;
delete p_tree;
return p_left_sub;
}

node* p_maxN = return_max(p_tree->p_left);
p_maxN->p_left = remove_max_node(p_tree->p_left, p_maxN);
p_maxN->p_right = p_tree->p_right;
delete p_tree;
return p_maxN;
}
else if(key < p_tree->key_value) {
p_tree->p_left = removeN(p_tree->p_left, key);
}
else {
p_tree->p_right = removeN(p_tree->p_right, key);
}
//--After all  changes have been done
return p_tree;
}

/*
*
* The entire implementation is sorted when calling return min and max
*
*
*/
node* sortedN(node* p_tree){
if (p_tree == NULL){return NULL;}

return sortedN(return_max(p_tree));
}

int main(int argv, char* []){

cout << "This is merely a test" << endl;
node myBinaryTree = {1};

if(search(&myBinaryTree,2)) {cout << "Node found" << endl;}
return 0;
}


My understanding is that the way I defined the other functions originally already sort and return the state of the node itself in a new way being that I am using pointers. Maybe I am wrong to think that my sorting function works. I have been with this all day and cannot think of a better way, most of my code was written for the understanding I have in it and the help of my books, my instructor is not being much help as well so I came here seeking some wisdom. (Originally posted in stack overflow but moved over here due to it working properly and only asking for a review and better implementation of the last algorithm)

# Bugs

In this line of your search function (in a previous version of the post, before the fix):

else if (p_tree->key_value = key) { return p_tree; }


you used = when you meant to use ==. You should always turn on full compiler warnings to help find errors like this.

In this line of the same function:

search(p_tree->p_left, key);


you forgot to use return as in:

 return search(p_tree->p_left, key);


Again, compiler warnings would have alerted you to this error.

# Infinite recursion

I'm not sure what sortedN() is supposed to do since your binary tree is already sorted. But what it actually does is recurse infinitely.

• ah thank you, the bug had been corrected. I had thought the same regarding the sortedN() function, I already had in my head that the algorithm was already sorted in the proper way by the implementation of the additional nodes being added to the list, I just was not sure enough about it. Any other suggestions would be greatly appreciated. – Alex_adl04 Sep 30 '15 at 4:38