Binary Search Tree

algorithm.md

###Binary Search Tree - Non-Linear Data Structure

A Binary Tree by nature, also known by ordered or sorted binary trees

####Constraints

• Since a Binary Tree, each node can have zero, one or a maximum of two children.
• The value contained in left-child must be lesser than or equal to the value of this node (parent).
• The value contained in right-child must be greater than or equal to the value of this node (parent).

####Binary Search Tree :: Searching

Since there are particular constraints while forming the search tree, we can apply the same during tree lookup. For an example if we are looking for a value that is lower than the key value of root, we can be sure of one thing - if the value do exist, it will be in the left subtree of this node.

BINARY_SEARCH_BST(x, value_to_search):
	WHILE x != NULL AND k != x.key:
		IF k < x.key:
			x = x.left
		ELSE:
			x = x.right
		END IF
	END WHILE
	RETURN x
END BINARY_SEARCH_BST

####Binary Search Tree :: Insertion

INSERT_NODE(T, NODE z):
	/* Inserts Node z at it's appropriate position in the Binary Search Tree */

	y = NULL
	x = T.root

	WHILE x != NULL:
		y = x
		IF z.key < x.key:
			x = x.left
		ELSE:
			x = x.right
	END WHILE

	z.parent = y

	IF y == NULL:
		T.root = z // Tree T is empty, First element
	ELSE IF z.key < y.key:
		y.left = z
	ELSE
		y.right = z
	END IF

END INSERT

####Binary Search Tree :: Deletion

For Deletion, there might be few tricky cases like nodes with children. Hence the logic has been divided into two sub modules.
The TRANSPLANT method replaces one node with another, along with the elements below them. Hence we are talking about replacing the subtree starting from NODE u, with the subtree starting with NODE v.
[ Yes there might be cases where u or v do not have any further children, then it's like replacing node u with node v ]

TRANSPLANT(TREE T, NODE u, NODE v) :
	IF u.parent = NULL:
		T.root = v
	ELSE IF u == u.parent.left :
		u.parent.left = v
	ELSE :
		u.parent.right = v
	END IF

	IF v != NULL:
		v.parent = u.parent
	END IF
END TRANSPLANT

The method MINIMUM_NODE finds out the node with minimum key value. In this case, the minimum will always be contained in the lowest left-most node.

MINIMUM_NODE:
	
	WHILE x.left != NULL
		x = x.left
	END WHILE

	RETURN x
END MINIMUM_NODE

Making use of the TRANSPLANT and MINIMUM_NODE, the DELETE_NODE method removes a node from the tree, making required changes along with leaving the resultant in form of Binary Search Tree.

DELETE_NODE(TREE T, NODE z):
	
	IF z.left == NULL:
		TRANSPLANT(T, z, z.right)
	ELSE IF z.right == NULL:
		TRANSPLANT(T, z, z.left)
	ELSE:
		y = MINIMUM_NODE(z.right)
		IF y.parent != z:
			TRANSPLANT(T, y, y.right)
			y.right = z.right
			y.right.parent = y

			TRANSPLANT(T, z, y)
			y.left = z.left
			y.left.parent = y
		END IF
	END IF
END DELETE_NODE

####Binary Search Tree :: Traversal

For traversal, we will be using Inorder Traversal on the tree.

TRAVERSE_BST(TREE T):

	IF T.root != NULL:
		TRAVERSE_BST(T.left)
		PRINT "NODE z :: z.key = " + T.key
		TRAVERSE_BST(T.right)
	END IF
END TRAVERSE_BST

While searching and inserting elements, after every comparission the problem set reduces to half of its previous and hence yields a conclusion within O(log n).
The method MINIMUM_NODE depends upon the height of tree emerging from that node and thus can take upto O(h), where h is the height of the concerned tree.
During the deletion operation, the node to be deleted is already supplied. It makes use of TRANSPLANT [which has a constant time complexity] and MINIMUM_NODE [complexity O(h)]. Therefore it runs in O(h) for a tree of height h.

BinarySearchTree.c

/*
	BINARY SEARCH TREE
	Iterative Approach
	Keeps a track of parent too
	** for TURBO C, remove // from commented statements
*/

#include<stdio.h>
#include<malloc.h>
//#include<conio.h>

/* Node structure defination */
struct element {
	int key;
	struct element *parent;
	struct element *left;
	struct element *right;
};
typedef struct element NODE;

NODE* BINARY_SEARCH_BST(NODE *x, int value_to_search){
	while(x != NULL && value_to_search != x->key){
		if(value_to_search < x->key)
			x = x->left;
		else
			x = x->right;
	}
	return x;
}

void INSERT_NODE(NODE **T, NODE *z){
	NODE *y = NULL;
	NODE *x = *T;

	while(x != NULL){
		y = x;
		if(z->key < x->key)
			x = x->left;
		else
			x = x->right;
	}

	z->parent = y;

	if(y == NULL)
		*T = z;
	else if(z->key < y->key)
		y->left = z;
	else
		y->right = z;
}

void TRANSPLANT(NODE **T, NODE *u, NODE *v){
	if(u->parent == NULL)
		*T = v;
	else if(u == u->parent->left)
		u->parent->left = v;
	else
		u->parent->right = v;

	if(v != NULL)
		v->parent = u->parent;
}

NODE* MINIMUM_NODE(NODE *x){
	while(x->left != NULL)
		x = x->left;

	return x;
}

void DELETE_NODE(NODE **T, NODE *z){
	NODE *y;
	if(z->left == NULL)
		TRANSPLANT(T, z, z->right);
	else if(z->right == NULL)
		TRANSPLANT(T, z, z->left);
	else{
		y = MINIMUM_NODE(z->right);
		y->right = z->right;
		y->right->parent = y;

		TRANSPLANT(T, z, y);
		y->left = z->left;
		y->left->parent = y;
	}
}

void TRAVERSE_BST(NODE *T){
	if(T != NULL){
		TRAVERSE_BST(T->left);
		printf("%d ", T->key);
		TRAVERSE_BST(T->right);
	}
}

NODE* new_node(int key){
	NODE *z = (NODE *) malloc(sizeof(NODE));
	z->key = key;
	z->parent = z->left = z->right = NULL;
	return z;
}

int main(){
	int ch = 0, element;
	NODE *root = NULL; /* Initial condition */
	NODE *temp;

	//clrscr();

	do{
		printf("\n\nAvailable Operations:\n1. INSERT\n2. DELETE\n3. TRAVERSE\n4. SEARCH\n5. QUIT");
		printf("\nEnter your choice (1 - 5): "); scanf("%d", &ch);
		switch(ch){
			case 1:
				printf("\nEnter an element to insert: ");  scanf("%d", &element);
				temp = new_node(element); INSERT_NODE(&root, temp);
				printf("\nTREE STATUS ::\n\t"); TRAVERSE_BST(root);
			break;
				
			case 2:
				printf("\nEnter an element to delete: ");  scanf("%d", &element);
				temp = BINARY_SEARCH_BST(root, element);
				if(temp != NULL)
					DELETE_NODE(&root, temp);
				else
					printf("No such element found");					
				printf("\nTREE STATUS ::\n\t"); TRAVERSE_BST(root);
			break;

			case 3:
				printf("\nTREE TRAVERSAL ::\n\t"); TRAVERSE_BST(root);
			break;

			case 4:
				printf("\nEnter an element to search for: ");  scanf("%d", &element);
				temp = BINARY_SEARCH_BST(root, element);
				if(temp != NULL)
					printf("%d exists in the tree.", element);
				else
					printf("No such element found.");
				printf("\nTREE STATUS ::\n\t"); TRAVERSE_BST(root);
			break;

			case 5: break;

			default:
				printf("\nInvalid options! Choose between [1,2,3,4,5]");
		}
	}while(ch != 5);

	printf("\n");
	//getch();
	return 0;
}

BinarySearchTree.java

/*
	BINARY SEARCH TREE
	Iterative Approach
	dynamic memory allocation
	Keeps a track of parent too
	Save File as BinarySearchTree.java
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class NODE{
	/* Node defination and related methods */
	/* Why static variables and methods? Since we are working with a single tree here
	  and making static makes it easier to invoke. */

	int key;
	NODE parent;
	NODE left;
	NODE right;

	public static NODE root;

	public NODE(int key){
		this.key = key;
		this.parent = this.left = this.right = null;
	}

	public static NODE BINARY_SEARCH_BST(NODE x, int value_to_search){
		while(x != null && value_to_search != x.key){
			if(value_to_search < x.key)
				x = x.left;
			else
				x = x.right;
		}
		return x;
	}

	public static void INSERT_NODE(NODE T, NODE z){
		NODE y = null;
		NODE x = T.root;

		while(x != null){
			y = x;
			if(z.key < x.key)
				x = x.left;
			else
				x = x.right;
		}

		z.parent = y;

		if(y == null)
			root = z;
		else if(z.key < y.key)
			y.left = z;
		else
			y.right = z;
	}

	public static void TRANSPLANT(NODE T, NODE u, NODE v){
		if(u.parent == null)
			T.root = v;
		else if(u == u.parent.left)
			u.parent.left = v;
		else
			u.parent.right = v;

		if(v != null)
			v.parent = u.parent;
	}

	public static NODE MINIMUM_NODE(NODE x){
		while(x.left != null)
			x = x.left;

		return x;
	}

	public static void DELETE_NODE(NODE T, NODE z){
		if(z.left == null)
			TRANSPLANT(T, z, z.right);
		else if(z.right == null)
			TRANSPLANT(T, z, z.left);
		else{
			NODE y = MINIMUM_NODE(z.right);
			y.right = z.right;
			y.right.parent = y;

			TRANSPLANT(T, z, y);
			y.left = z.left;
			y.left.parent = y;
		}
	}

	public static void TRAVERSE_BST(NODE T){
		if(T != null){
			TRAVERSE_BST(T.left);
			System.out.print(T.key + " ");
			TRAVERSE_BST(T.right);
		}
	}
}

public class BinarySearchTree{
	public static void main(String s[]) throws NumberFormatException, IOException{
		
		BufferedReader ip = new BufferedReader(new InputStreamReader(System.in));

		int ch = 0, element; NODE temp;

		NODE T = new NODE(0); /* Taking a blank node as reference to tree */
			/* Although its not required. Here it is used to keep consistency with the algorithm provided*/
		T.root = null;  /* Initial condition */

		do{
			System.out.print("\n\nAvailable Operations:\n1. INSERT\n2. DELETE\n3. TRAVERSE\n4. SEARCH\n5. QUIT");
			System.out.print("\nEnter your choice (1 - 5): "); ch = Integer.parseInt(ip.readLine());
			switch(ch){
				case 1:
					System.out.print("\nEnter an element to insert: ");	element = Integer.parseInt(ip.readLine());
					temp = new NODE(element); NODE.INSERT_NODE(T.root, temp);
					System.out.print("\nTREE STATUS ::\n\t"); NODE.TRAVERSE_BST(T.root);
				break;
					
				case 2:
					System.out.print("\nEnter an element to delete: ");	element = Integer.parseInt(ip.readLine());
					temp = NODE.BINARY_SEARCH_BST(T.root, element);
					if(temp != null)
						NODE.DELETE_NODE(T.root, temp);
					else
						System.out.print("No such element found");					
						System.out.print("\nTREE STATUS ::\n\t"); NODE.TRAVERSE_BST(T.root);
				break;

				case 3:
					System.out.print("\nTREE TRAVERSAL ::\n\t"); NODE.TRAVERSE_BST(T.root);
				break;

				case 4:
					System.out.print("\nEnter an element to search for: ");	element = Integer.parseInt(ip.readLine());
					temp = NODE.BINARY_SEARCH_BST(T.root, element);
					if(temp != null)
						System.out.print(element + " exists in the tree.");
					else
						System.out.print("No such element found.");
					System.out.print("\nTREE STATUS ::\n\t"); NODE.TRAVERSE_BST(T.root);
				break;

				case 5: break;

				default:
					System.out.print("\nInvalid options! Choose between [1,2,3,4,5]");
			}
		}while(ch != 5);

		System.out.print("\n");
	}
}