Insert element in a binary tree. Simple Java example.

How to insert an element in a binary tree in Java? That is one of the common questions in any technical interview. The basic logic here is to put elements that value less than the root on the binary tree’s left side. And put the elements that value more than the root element on the right side of the tree. To make it happen, we should write a function based on the recursion.

A critical thing you should keep in mind.

While we are running the recursion, we have to remember about the call stack. You should know how the program is operating the code during recursion.

Code example of how to add an element in a binary tree? The complete solution in Java.

If you implemented the binary tree and want to add the element, you should follow the next steps: 

• Check if the node equals null. That “if” condition is the point where the new element is added. Here, we need to create a new node and set the value to it;

           if (node == null){
                node = new TreeNode(value);
                return node;
            }

• If the first “if” condition returned false, we are coming to the second “if” condition. If we are here, that means the passed node as a parameter was not null. That’s why we can check it’s value. If the new node’s value is less than the current node’s value, we should recursively rerun the function. As a parameter, we should pass the new node’s value and the left node of the current node. As we move our running to the left side of the tree;

                if (value < node.data){
                node.left = insert(node.left, value);

• Otherwise, the new element’s value is more than the value of the current element’s value. That means we should run to the right side. Just make a recursion call, and as a parameter, we should pass the right node of the current node and the value of the new node; 

              } else {
                node.right = insert(node.right, value);
              }

As a result, that function will run itself until it will find the empty (null) space to create a new node and put it there. In this article you figured out, how to insert an element in a binary tree (Java).

Animated:

Step-by-step schema:

Full code:

private TreeNode insert(TreeNode node, int value){
//Here we creating a new node
            if (node == null){
                node = new TreeNode(value);
                return node;
            }
//Going to the left side of the current node
            if (value < node.data){
                node.left = insert(node.left, value);
            } else {
//Going to the right side of the current node
                node.right = insert(node.right, value);
            }
            return node;
        }

Full code and more examples in my facebook group.

Useful links:

• How to implement a binary tree in Java
• Pre-order traversal example
• In order traversal sample
• Post-order traversal Java example