How would you insert an element into a Binary Search Tree?

Insertion into a Binary Search Tree will happen using the rule of L<N<R. You would compare the new element with the root and based on it being greater or smaller than the root value it goes to right or left. If the new element is equal to the root value then it goes to the right side. This will continue till the element doesn't have an element greater than or smaller than itself.
The same is explained in the pseudo code below. You can execute this iteratively or recursively.


	node=root
	if (element.value>=node.value){
		if (node.right==null){
			//add element as right child
		} else{
			//redo the logic with node=node.right
		}
	}
	else{
		if (node.left==null){
			//add element as left child
		} else{
			//redo the logic with node=node.left
		}
	}

 

To represent the following BST and do insertions you can go through the example

 

Definition of the TreeNode class


class TreeNode{
	int value;
	TreeNode left;
	TreeNode right;		

    public static boolean insert(TreeNode root, TreeNode n){
        if (n!=null){
            if (n.value>=root.value){
                if (root.right==null){
                    root.right=n;
                    return true;
                }
                else{
                    return insert(root.right,n);
                }
            }
            else{
                if (root.left==null){
                    root.left=n;
                    return true;
                }
                else{
                    return insert(root.left,n);
                }
            }
        }
        return false;
    }

	public TreeNode(int x){
		value=x;
	}
}

 

Test code for the insertion.


public class BSTUtil {
	public static void main(String[] args) {
        TreeNode root=new TreeNode(8);
        TreeNode.insert(root, new TreeNode(3));
        TreeNode.insert(root, new TreeNode(10));
        TreeNode.insert(root, new TreeNode(6));
        TreeNode.insert(root, new TreeNode(1));
        TreeNode.insert(root, new TreeNode(14));
        TreeNode.insert(root, new TreeNode(4));
        TreeNode.insert(root, new TreeNode(7));
        TreeNode.insert(root, new TreeNode(13));
	}
}

This will result in the BST mentioned in the diagram

core java 12

FOLLOW US ON LinkedIn



Explore Tutu'rself