# Binary Search Tree (BST) Complete Implementation.

**Binary Tree :** A data structure in which we have nodes containing data and two references to other nodes, one on the left and one on the right.

Binary Tree consist of Nodes

- Nodes are nothing but objects of a class and each node has data and a link to the left node and right node.
- Usually we call the starting node of a tree as
*root*.

class Node{ int data; Node left; Node right; public Node(int data){ this.data = data; left = null; right = null; } }

- Left and right node of a Leaf node points to NULL so you will know that you have reached to the end of the tree.

**Binary Search Tree:**

Often we call it as BST, is a type of Binary tree which has a special property.

*Nodes smaller than root goes to the left of the root and Nodes greater than root goes to the right of the root*.

**Operations:**

**Insert(int n) :** Add a node the tree with value n. Its O(lgn)

**Find(int n) :** Find a node the tree with value n. Its O(lgn)

**Delete (int n) **: Delete a node the tree with value n. Its O(lgn)

**Display**(): Prints the entire tree in increasing order. O(n).

Detail Explanations for the Operations:

**Find(int n):**

- Its very simple operation to perform.
- start from the root and compare root.data with n
- if root.data is greater than n that means we need to go to the left of the root.
- if root.data is smaller than n that means we need to go to the right of the root.
- if any point of time root.data is equal to the n then we have found the node, return true.
- if we reach to the leaves (end of the tree) return false, we didn’t find the element

- Very much similar to find() operation.
- To insert a node our first task is to find the place to insert the node.
- Take current = root .
- start from the current and compare root.data with n
- if current.data is greater than n that means we need to go to the left of the root.
- if current.data is smaller than n that means we need to go to the right of the root.
- if any point of time current is null that means we have reached to the leaf node, insert your node here with the help of parent node. (See code)

**Delete(int n):**

Complicated than Find() and Insert() operations. Here we have to deal with 3 cases.

- Node to be deleted is a leaf node ( No Children).
- Node to be deleted has only one child.
- Node to be deleted has two childrens.

**Node to be deleted is a leaf node ( No Children).**

its a very simple case, if a node to be deleted has no children then just traverse to that node, keep track of parent node and the side in which the node exist(left or right) and set *parent.left = null or parent.right = null;*

**Node to be deleted has only one child.**

- its a slightly complex case. if a node to be deleted(deleteNode) has only one child then just traverse to that node, keep track of parent node and the side in which the node exist(left or right).
- check which side child is null (since it has only one child).
- Say node to be deleted has child on its left side . Then take the entire sub tree from the left side and add it to the parent and the side on which deleteNode exist, see step 1 and example.

**Node to be deleted has two children.**

Now this is quite exciting π

You just cannot replace the deleteNode with any of its child, Why? Lets try out a example.

**What to do now?????**

Dont worry we have solution for this π

**Find The Successor:**

Successor is the node which will replace the deleted node. Now the question is to how to find it and where to find it.

*Successor is the smaller node in the right sub tree of the node to be deleted.*

**Display()** : To know about how we are displaying nodes in increasing order, Click Here

Complete Example :

**Complete Example Code:**

Output:Original Tree : 1 2 3 4 6 8 9 10 15 16 20 25 Check whether Node with value 4 exists : true Delete Node with no children (2) : true 1 3 4 6 8 9 10 15 16 20 25 Delete Node with one child (4) : true 1 3 6 8 9 10 15 16 20 25 Delete Node with Two children (10) : true 1 3 6 8 9 15 16 20 25