Binary Search Tree

binary_tree_mod.cc

// Author: Dron Rathore <dron(.)rathore[(@)]G-Mail>
// A modified C++ implementation for Binary Search Tree
// Every node keeps a parent node ref to help the deletion
// in Θ(log(n)) complexity.

// This is no rocket science, same can be acheived with
// double pointers where you perform a look ahead search in
// the tree in case of deletion so you have parent of the
// Right Subtree's largest node which comes handy.

#include <iostream>
using namespace std;

typedef struct node
{
	node* left;
	node* right;
	node* parent;
	int val;
}Node;

Node* insertInBTree(Node* tree, int val){
	Node* nextNode, *currentNode;
	nextNode = currentNode = tree;
	Node* newNode = (struct node *)malloc(sizeof(struct node));
	newNode->right = newNode->left = newNode->parent = NULL;
	newNode->val = val;
	while (nextNode != NULL){
		if (nextNode != NULL){
			currentNode = nextNode;
		}
		if (currentNode->val > val){
			nextNode = nextNode->left;
		} else {
			nextNode = nextNode->right;
		}
		
	}
	if (tree == NULL){
		return newNode;
	}
	if (currentNode->val > val){
		currentNode->left = newNode;
	} else {
		currentNode->right = newNode;
	}
	newNode->parent = currentNode;
	return tree;
}

Node* getHighestOfRightSubTree(Node* stree){
	if (stree->left == NULL) {
		// this is the end node
		return NULL;
	}
	Node* subtree = stree->left;
	while(subtree && subtree->right != NULL){
		if (subtree->right != NULL)
			subtree = subtree->right;
		else
			break;
	}
	return subtree;
}

Node* searchInBTree(Node *tree, int val){
  bool found = false;
  Node* current = tree;
  while (found != true || current != NULL){
    if (current->val < val){
      current = current->right;
    } else if (current->val > val) {
      current = current->left;
    } else  if (current->val == val){
      return current;
    }
  }
  return NULL;
}

Node* deleteFromBTree(Node** root, int val){
  /* empty tree */
	if (*root == NULL){
		return *root;
	}

	Node* current = *root;
	while (current != NULL){
    /* found the match */
		if (current->val == val){
      /* get the highest node from left subtree */
			Node* highest = getHighestOfRightSubTree(current);
      /* no highest node found, we are either a leaf or a right skewed root */
			if (highest == NULL){
        /* this is a root node  that we are removing */
				if (current->parent == NULL){
          /* is it a lonely root node tree? */
					if (current->right == NULL){
						free(*root);
						*root = NULL;
						return *root;
					} else {
            /* make its right node the new root */
            *root = current->right;
            current->right->parent = NULL;
            return *root;
          }
				}

        /* this is a leaf with nothing on left */
        /* do we have something on right? */
        if (current->right != NULL){
          current->right->parent = current->parent;
          if (current->parent->val > current->val){
            current->parent->left = current->right;
          } else {
            current->parent->right = current->right;
          }
          free(current);
          return *root;
        } else {
          /* pure leaf with nothing on left as well as right */
          if (current->parent->val > current->val){
            current->parent->left = NULL;
          } else {
            current->parent->right = NULL;
          }
          free(current);
          return *root;
        }
			}
			// found the highest node
			// lets replace with highest

			if (current->parent == NULL){
				// removing root
				current->val = highest->val;
        if (highest->parent->val != current->val){
          // not immediate node
				  highest->parent->right = highest->left;
          highest->left->parent = highest->parent;
        }
        else if (highest->left != NULL){
          // immediate node
          current->left = highest->left;
          highest->left->parent = current;
        }
				free(highest);
				return *root;
			}

			// removing ordinary node
			current->val = highest->val;
			highest->parent->right = highest->left;
			free(highest);
			return *root;

		} else if (current->val > val){
			current = current->left;
		} else {
			current = current->right;
		}
	}
	return *root;
}

void printTree (Node* root){
	if (root == NULL){
		return;
	}
	printTree(root->left);
	cout<< root->val << ", ";
	printTree(root->right);
}
int main(int argc, char const *argv[])
{
	Node* root = insertInBTree(NULL, 23);
	insertInBTree(root, 12);
	insertInBTree(root, 56);
	insertInBTree(root, 90);
	insertInBTree(root, 40);
	insertInBTree(root, 32);
	insertInBTree(root, 49);
	insertInBTree(root, 10);
	insertInBTree(root, 11);
	printTree(root);
	cout << endl;
	deleteFromBTree(&root, 23);
	deleteFromBTree(&root, 56);
	deleteFromBTree(&root, 10);
	deleteFromBTree(&root, 11);
	deleteFromBTree(&root, 12);
	printTree(root);
	cout << endl;
	insertInBTree(root, 56);
	insertInBTree(root, 11);
	insertInBTree(root, 12);
  insertInBTree(root, 23);
	printTree(root);
	cout << endl;
	Node* singleNodeTree = insertInBTree(NULL, 23);
  insertInBTree(singleNodeTree, 33);
  insertInBTree(singleNodeTree, 43);
  insertInBTree(singleNodeTree, 53);
	printTree(singleNodeTree);
	cout << endl;
	deleteFromBTree(&singleNodeTree, 33);
	printTree(singleNodeTree);
  Node* foundNode = searchInBTree(singleNodeTree, 43);
  cout << endl;
  printTree(foundNode);
	return 0;
}