Binary Search Tree 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

Insert(int n):

  • 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.

  1. 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).
  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 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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

  • Garima

    Very Easy to understand!!
    Gud Explantion 🙂

    • Sumit Jain

      Thanks Garima 🙂

  • Damaris Perez

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

    • tutorialhorizon

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

      • Damaris Perez

        But won’t the successor 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. 🙂

        • tutorialhorizon

          Can u give one example, it will be easy to understand.

          • Damaris Perez

            Oh, no. I understand it now. I was just confused because I was looking for everything in getSuccessor(). So, I thought if the node to be deleted had no right children, then the right most child of the left branch became the successor, but that is all done in delete(), so I understand everything, now. Thank you.

          • tutorialhorizon

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

  • siva

    for insert, we traverse elements until current not equal to null. so i changed condition for while loop current!=null instead or true. the loop goes infinite times. but why? can anyone help

  • Komal Shipe

    What will happen if you add two nodes of same value?

  • Rotem Uzan

    Hi,
    I have a question, in the Delete() method, why we can’t just use the insert method and run it on the children of the deleted node ?
    it is because of the different order we will receive ?
    Thanks !

  • Prashant Bisht

    I dont understand what is the significance of parent=current in insert .I think it will work without this line also.

  • Suchith S Pillai

    For Delete, No children if(current.left==null && current.right==null){ current = null;} will do the deletion right ? Or we need the if conditions given ?

    • Eldo Joseph

      Nope. current’s parent should set either parent.left = null or parent.right = null.
      setting current = null would only nullify the value in your current pointer, this does nothing in the tree.

      • Suchith S Pillai

        Please correct my understanding: Current Indicates a child node. So it will be either parent.left==current or parent.right==current, Since it is an existing BST. SO what is the difference between parent.left = null and current = null, since both referes to the same object.

        • Eldo Joseph

          when u set current = null, u r just removing the reference of the current variable to the child node. Notice that, after doing this the node is actually in memory and only the current pointer’s reference to it has been removed. But the parent pointer is still pointing to that node.

          (In garbage collected languages, like java and python, since the parent is still pointing to the node, it won’t be removed. I don’t know if c works differently though)

  • Tạ Anh Tú

    Thanks. This post is very useful for me!

  • Nkululeko Rwaxa

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

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

    Time complexity is completely wrong.

    Insert O(N) Θ(logN),
    delete O(N) Θ(logN),
    find O(N) Θ(logN),
    display O(N) Θ(N)

    AVL trees have the complexity you said above…

    also we usually using logN instead of lgN to express the time complexity.

  • Ibrahim Babangida

    QUESTION:

    A company wishes to keep
    record of its products updated, sorted and capable of being search rapidly.
    Each product is described by Prod Id, Prod description quality, unit price. If
    each product details are to be kept in a Binary search tree, write:

    1) A
    binary search tree declaration that can be used to store product information.

    2) A
    method called insert() that can be used to insert a product 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 product detail.

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

  • amr ras

    Why is the root declared static? Wouldn’t that mean if we made two instances of BSTs, they’d share the same root?

%d bloggers like this: