Question 69 : Can you write algorithm to insert a node in binary search tree

 

Binary search tree is a special type of Binary tree which have following properties.

• Nodes which are smaller than root will be in left subtree.
• Nodes which are greater than root will be right subtree.
• It should not have duplicate nodes
• Both left and right subtree also should be binary search tree.

Example of binary search tree:

Lets perform following operation on binary search tree

• Find
• Insert

Search()

Searching a node in binary search is very easy. You just need to traverse left (if smaller) and right (if greater) according to value to be found.

Algorithm:

• If node to be found is equal to root, then search is successful
• If node to be found is smaller than root , then traverse left subtree.
• If node to be found is greater than root, then traverse right subtree
• Repeat above steps recursively until you find the node.

Insert()

Insert node operation is also easy operation. You just need to compare it with root and traverse left (if smaller) or right(if greater) according to value of node to be inserted.

Algorithm:

• Make root node as current node
• If node to be inserted < root
  • If it has left child then traverse left
  • If it do not have left child, insert node here
• If node to be inserted > root
  • If it have right child, traverse right
  • If it do not have right child, insert node here.

Complete java program:

public class BinarySearchTreeMain {
    public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }
 
    public static boolean search(TreeNode root,TreeNode nodeToBeSearched)
    {
        if(root==null)
            return false;
        if(root.data== nodeToBeSearched.data)
        {
            return true;
        }
        boolean result=false;
 
        if(root.data > nodeToBeSearched.data)
            result=search(root.left,nodeToBeSearched);
        else if(root.data < nodeToBeSearched.data)
            result= search(root.right,nodeToBeSearched);
 
        return result;
    }
 
    public static TreeNode insert(TreeNode root,TreeNode nodeToBeInserted)
    { if(root==null) {
        root=nodeToBeInserted; return root;
    } if(root.data > nodeToBeInserted.data)
    {
        if(root.left==null)
            root.left=nodeToBeInserted;
        else
            insert(root.left,nodeToBeInserted);
    }
    else if(root.data < nodeToBeInserted.data)
        if(root.right==null)
            root.right=nodeToBeInserted;
        else
            insert(root.right,nodeToBeInserted);
    return root;
    }
 
    public static void inOrder(TreeNode root)
    {
        if(root==null)
            return;
        inOrder(root.left);
        System.out.print(root.data+" ");
        inOrder(root.right);
    }
    public static void main(String[] args)
    {
 
        // Creating a binary search tree
        TreeNode rootNode=createBinarySearchTree();
        TreeNode node55=new TreeNode(55);
        boolean result=search(rootNode,node55);
        System.out.println("Searching for node 55 : "+result);
        System.out.println("---------------------------");
        TreeNode node13=new TreeNode(13);
        TreeNode root=insert(rootNode,node13);
        System.out.println("Inorder traversal of binary tree after adding 13:");
        inOrder(root);
 
    }
 
    public static TreeNode createBinarySearchTree()
    {
        TreeNode rootNode =new TreeNode(40);
        TreeNode node20=new TreeNode(20);
        TreeNode node10=new TreeNode(10);
        TreeNode node30=new TreeNode(30);
        TreeNode node60=new TreeNode(60);
        TreeNode node50=new TreeNode(50);
        TreeNode node70=new TreeNode(70);
        TreeNode node5=new TreeNode(5);
        TreeNode node55=new TreeNode(55);
 
        insert(null,rootNode);
        insert(rootNode,node20);
        insert(rootNode,node10);
        insert(rootNode,node30);
        insert(rootNode,node60);
        insert(rootNode,node50);
        insert(rootNode,node70);
        insert(rootNode,node5);
        insert(rootNode,node55);
        return rootNode;
    }
 
}

When you run above program, you will get below output:

Searching for node 55 : true
---------------------------
Inorder traversal of binary tree after adding 13:
5 10 13 20 30 40 50 55 60 70

Don't miss the next article! 
Be the first to be notified when a new article or Kubernetes experiment is published.                            

 

 Share This

• Facebook

• Twitter

• Linkedin

• Pinterest