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

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 is not balanced and 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.

CodePudding user response：

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  );
        }