# Binary Search Tree Complete Implementation.

Binary Tree : A data struc­ture in which we have nodes con­tain­ing data and two ref­er­ences to other nodes, one on the left and one on the right.

Binary Tree con­sist of Nodes

• Nodes are noth­ing but objects of a class and each node has data and a link to the left node and right node.
• Usu­ally we call the start­ing 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 spe­cial property.

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

Oper­a­tions:

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)

Dis­play(): Prints the entire tree in increas­ing order. O(n).

Detail Expla­na­tions for the Operations:

Find(int n):

• Its very sim­ple oper­a­tion to perform.
• start from the root and com­pare 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

Insert(int n):

• Very much sim­i­lar to find() operation.
• To insert a node our first task is to find the place to insert the node.
• Take cur­rent = root .
• start from the cur­rent and com­pare 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 cur­rent is null that means we have reached to the leaf node, insert your node here with the help of par­ent node. (See code)

Delete(int n):

Com­pli­cated than Find() and Insert() oper­a­tions. 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 sim­ple case, if a node to be deleted has no chil­dren then just tra­verse to that node, keep track of par­ent 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.

1. its a slightly com­plex case. if a node to be deleted(deleteNode) has only one child then just tra­verse to that node, keep track of par­ent node and the side in which the node exist(left or right).
2. check which side child is null (since it has only one child).
3. 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 par­ent and the side on which deleteN­ode exist, see step 1 and example.

Node to be deleted has two childrens.

Now this is quite exciting 🙂

You just can­not replace the deleteN­ode with any of its child, Why? Lets try out a example.

What to do now?????

Dont worry we have solu­tion for this 🙂

Find The Successor:

Suc­ces­sor is the node which will replace the deleted node. Now the ques­tion is to how to find it and where to find it.

Suc­ces­sor is the smaller node in the right sub tree of the node to be deleted.

Dis­play() : To know about how we are dis­play­ing nodes in increas­ing order, Click Here

Com­plete Example :

Com­plete Exam­ple 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
```

#### You may also like...

• Garima

Very Easy to under­stand!!
Gud Explantion 🙂

• Sumit Jain

Thanks Garima 🙂

• Damaris Perez

Hello, I don’t think this works if you want to get a suc­ces­sor for a node that has no right children.

• tuto­ri­al­hori­zon

That will be the case when node has only one child , 2nd case in dele­tion. In that it will not find the successor.

• Damaris Perez

But won’t the suc­ces­sor then become the right most child of the left?

• Damaris Perez

But I do see it, now. That it’s in the delete method. Thank you for your quick reply. 🙂

• tuto­ri­al­hori­zon

Can u give one exam­ple, it will be easy to understand.

• Damaris Perez

Oh, no. I under­stand it now. I was just con­fused because I was look­ing for every­thing in get­Suc­ces­sor(). So, I thought if the node to be deleted had no right chil­dren, then the right most child of the left branch became the suc­ces­sor, but that is all done in delete(), so I under­stand every­thing, now. Thank you.

• tuto­ri­al­hori­zon

Glad that its clear now. let me know if you find issues in other posts.

• siva

for insert, we tra­verse ele­ments until cur­rent not equal to null. so i changed con­di­tion for while loop current!=null instead or true. the loop goes infi­nite times. but why? can any­one help

• Komal Shipe

What will hap­pen if you add two nodes of same value?

• Rotem Uzan

Hi,
I have a ques­tion, in the Delete() method, why we can’t just use the insert method and run it on the chil­dren of the deleted node ?
it is because of the dif­fer­ent order we will receive ?
Thanks !

• Prashant Bisht

I dont under­stand what is the sig­nif­i­cance of parent=current in insert .I think it will work with­out this line also.

• Suchith S Pillai

For Delete, No chil­dren if(current.left==null && current.right==null){ cur­rent = null;} will do the dele­tion right ? Or we need the if con­di­tions given ?

• Eldo Joseph

Nope. current’s par­ent should set either parent.left = null or parent.right = null.
set­ting cur­rent = null would only nul­lify the value in your cur­rent pointer, this does noth­ing in the tree.

• Suchith S Pillai

Please cor­rect my under­stand­ing: Cur­rent Indi­cates a child node. So it will be either parent.left==current or parent.right==current, Since it is an exist­ing BST. SO what is the dif­fer­ence between parent.left = null and cur­rent = null, since both ref­eres to the same object.

• Eldo Joseph

when u set cur­rent = null, u r just remov­ing the ref­er­ence of the cur­rent vari­able to the child node. Notice that, after doing this the node is actu­ally in mem­ory and only the cur­rent pointer’s ref­er­ence to it has been removed. But the par­ent pointer is still point­ing to that node.

(In garbage col­lected lan­guages, like java and python, since the par­ent is still point­ing to the node, it won’t be removed. I don’t know if c works dif­fer­ently though)

• Tạ Anh Tú

Thanks. This post is very use­ful for me!

• Nku­l­uleko Rwaxa

About the 3rd case on Delete(), is the Suc­ces­sor not 12 instead of 16 ?
I think it is 12 though

• Μπάμπης Μπιλλίνης

Time com­plex­ity is com­pletely wrong.

Insert O(N) Θ(logN),
delete O(N) Θ(logN),
find O(N) Θ(logN),
dis­play O(N) Θ(N)

AVL trees have the com­plex­ity you said above…

also we usu­ally using logN instead of lgN to express the time complexity.

• Ibrahim Babangida

QUESTION:

A com­pany wishes to keep
record of its prod­ucts updated, sorted and capa­ble of being search rapidly.
Each prod­uct is described by Prod Id, Prod descrip­tion qual­ity, unit price. If
each prod­uct details are to be kept in a Binary search tree, write:

1) A
binary search tree dec­la­ra­tion that can be used to store prod­uct information.

2) A
method called insert() that can be used to insert a prod­uct record in a tree

3) A
method called delete() that can be used to delete a product

4) A
method called update () to update a prod­uct detail.

5) Test
all your method in a pro­gram.
please i need help on this.
thanks