Binary search tree is an extension of linked list data structure that contains node. Insertion in tree is easy. This tree contains a root and child node where left hand sided node always lesser than parent node and right hand sided node always have greater value than parent node.

Insertion operation in tree takes time complexity of O(log(n)) in average cases and O(n) in worst cases.

Following is the example of insertion in BST :

structure of tree node :

public class TreeNode {

    private int value;
    private TreeNode leftNode;
    private TreeNode rightNode;

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public TreeNode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }

    public TreeNode getRightNode() {
        return rightNode;
    }

    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }
}

class to perform insert operation :

public class BSTOperations {

    private TreeNode leftNode = null;
    private TreeNode rightNode = null;
    private TreeNode root = null;

    public void insertTreeNode(int value){

        TreeNode newNode = new TreeNode();
        newNode.setValue(value);

        if (root == null){
            root = newNode;
            return;
        }

        TreeNode parentNode = null;
        TreeNode currentNode = root;

        while (true){

            parentNode = currentNode;

            Log.e("currentnode data :: ", currentNode.getValue() + "");

            if (value > currentNode.getValue()){

                currentNode = currentNode.getRightNode();

                if (currentNode == null) {

                    parentNode.setRightNode(newNode);
                    Log.e(" tree data :: ", parentNode.getValue() + "");

                    return;

                }

            }else{

                currentNode = currentNode.getLeftNode();

                if (currentNode == null){

                    parentNode.setLeftNode(newNode);
                    Log.e(" tree data :: ", parentNode.getValue() + "");

                    return;

                }
            }
        }
    }
}