How can I implement a recursive insert function for a binary tree?

Question

I want to emphasize that I am specifically dealing with a binary tree, not a binary search tree (BST). The only requirements I have for this tree is that it should be balanced and insert children from left to right. I do not care about it being ordered or having duplicates.

I ask this because most of the time I find examples of inserts for a binary tree, it is for a BST instead where there are no duplicates and we order things in a way that values less than the root node are stored at root.left and values that are higher than the root node get stored and root.right. I know how to implement that already, but would like to learn how to implement a basic insert for a regular binary tree. It is the recursive aspect that I am having difficulties with.

Also, I know it would be easier to do this using a data structure like a queue or a list but I would first like to attempt it without one.

Here is my insert function:

    TreeNode insert(int data, TreeNode root, boolean isLeft){

    if(root == null){
        root = new TreeNode(data);
    }
    else if(root.left == null){
        root.left = new TreeNode(data);
    }
    else if(root.right == null){
        root.right = new TreeNode(data);

    }
    else{
        if(isLeft){
            insert(data, root.right, false);
        }
        else{
            insert(data, root.left, true);
        }
    }
    return root;
}

And here is what I am using to initialize the tree:

public static void main(String[] args){

    TreeNode root = new TreeNode(1);

    boolean isLeft = false;

    for(int i = 2; i < 11; i++){
        isLeft = !isLeft;
       root = root.insert(i, root, isLeft);
    }

This produces a tree that looks like this:

│       ┌── 7
│   ┌── 3
│   │   └── 5
│   │       └── 9
└── 1
    │       ┌── 10
    │   ┌── 6
    │   │   └── 8
    └── 2
        └── 4

Which does not insert systematically from left to right. Ideally it would look like this:

│       ┌── 7
│   ┌── 3
│   │   └── 6
│   │        
└── 1
    │       
    │   ┌── 5
    │   │   └── 10
    └── 2   ┌── 9
        └── 4
            └── 8

The only reason it is numbered here is because I am using a for loop to create values but I do not care about number order, just left-to-right balance.

What is the purpose for this tree? If there is no meaning to where a value sits in that tree, then how will it benefit anything useful? — trincot
– trincot, Commented Dec 10, 2022 at 13:03
That looks balanced and somewhat systematic to me. Can you show the expected result? — Sweeper
– Sweeper, Commented Dec 10, 2022 at 13:03
I edited my original post to reflect what I am looking for out of the tree structure. — Mudpill
– Mudpill, Commented Dec 10, 2022 at 13:16

trincot · Accepted Answer · 2022-12-10 13:34:49Z

1

If you would maintain the size of the tree then the binary representation of that size (plus 1) reveals which path to take to the next insertion point.

For instance, if the current tree is:

then its size+1 is 5, which in binary is 101. Ignore the most significant bit -- which is always 1 -- and then interpret a 0 as left, and 1 as right. And indeed that is the path for reaching the spot where the next value must be injected:

          1
(left)  /   \
       2     3
      / \ (right)
     4   5

Not the question, but it is overkill to have a root parameter, when the function is a method on a TreeNode instance, so you already have the root (i.e. this).

Here is an implementation -- not recursive, as it is quite straightforward to do iteratively:

    TreeNode insert(int data, int size) {
        TreeNode root = this;
        String bits = Integer.toBinaryString((size + 1) >> 1).substring(1);
        for (char bit : bits.toCharArray()) {
            root = bit == '1' ? root.right : root.left;
        }
        if (root.left == null) {
            root.left = new TreeNode(data);
        } else {
            root.right = new TreeNode(data);
        }
        return this;
    }

Call as:

        TreeNode root = new TreeNode(1);
        int size = 1;
        for(int i = 2; i < 11; i++){
            root.insert(i, size++);
        }

answered Dec 10, 2022 at 13:34

trincot

357k38 gold badges282 silver badges339 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mudpill Over a year ago

Thank you, this works beautifully and it is an approach that I never would have considered. Someone asked earlier what the purpose of this, and to be honest, there is none. I just wanted to see how an implementation of this would look, and yours looks great.

Collectives™ on Stack Overflow

How can I implement a recursive insert function for a binary tree?

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related