Code Destine

Problem Statement

You have given a binary search tree and a value V, insert the value V into the binary search tree and return the root node of the modified BST. It is guaranteed that the value V does not exist in the BST.

Example 

Inserting 7 into above binary search tree.

Solution

To solve this problem, we will traverse the binary search tree using its ordering property (left child is smaller than parent and right child is greater than parent), to find out the place where the new element will be inserted.

Program 

public class Main {

	public static void main(String[] args) {
		Main main = new Main();

		TreeNode node = new TreeNode(5);
		node.left = new TreeNode(3);
		node.right = new TreeNode(8);		
		
		node.left.left = new TreeNode(2);
		node.left.right = new TreeNode(4);	
		
		node.right.right = new TreeNode(9);	
		
		TreeNode result = main.insertIntoBST(node, 7);
		main.print(result);
	}
	
	public void print(TreeNode node){        
        if(node == null) return;        
        print(node.left);
        System.out.print(node.val);
        print(node.right);
    }	
	
	public TreeNode insertIntoBST(TreeNode root, int val) {
        return findInsert(root, val);
    }
    
    public TreeNode findInsert(TreeNode node, int val){
        
        if(node == null){
            return new TreeNode(val);
        }        
        if(node.val < val){ 
            node.right = findInsert(node.right, val); 
        }else if(node.val > val){
            node.left = findInsert(node.left, val);
        }        
        return node;
    }
	
	public static class TreeNode {		
		int val;
		TreeNode left;
		TreeNode right;
		
		TreeNode(int x) {
			val = x;
		}
	}
}

Result

2345789

Similar Post

1. Same Tree
2. Sum of all Left Leaves
3. Level Order Traversal of Binary Tree

That’s all for Insert into a Binary Search Tree in Java, If you liked it, please share your thoughts in a comments section and share it with others too.