How to implement a Complete Binary Tree using recursion without comparing the value of the node?

Question

public void recurInsert(BinaryTree.Node root, BinaryTree.Node newNode, int height) {
    if (newNode == null) {
        System.out.println("InsertNode is empty, please create new one");
        return;
    }
    else{
        if (height == 1) {
            if (root == null)
                return;
            else if (root.leftChild == null) {
                root.leftChild = newNode;
                System.out.println("left" + newNode.data);
            }
            else {
                root.rightChild = newNode;
                System.out.println("right" + newNode.data);
            }
        }
        else{
            if (root.leftChild != null)
                recurInsert(root.leftChild, newNode, height-1);
            //else (root.rightChild != null)
            //    recurInsert(root.rightChild, newNode, height-1);
            if (root.rightChild != null)
                recurInsert(root.rightChild, newNode, height-1);
        }
    }
}

This is the code I implemented, but it actually inserts two same nodes to make it balance. Can anyone help me to fix the bug or implement it in another way?

I just want to implement an insertion for a complete binary tree using recursion . Say inserting a node with a sequence A,B,C,D,E,F. It comes like root is A and its left child is B, and right child is C and B's children are D and E,and C's left child is F.

My code has bug but implemented this insertion to make the tree is binary complete tree. It comes like A's children are B and C. But B's children is D,E and C's children is D and E as well instead of F. So hope you guys can help me to fix the bug or to implement it in another way using recursion.

Fortunately. I've seen a similar question posted on Stack Overflow, but I want to implement it using recursion, not with additional data structure.

Answer 1

The recursive method just implicitly implements the explicit stack from the example you linked to. The C# program below shows how it's done. I assume you can convert to Java easily enough.

Note that the TreeInsert method assumes that the root node is not null.

    public class TreeNode
    {
        public TreeNode Left;
        public TreeNode Right;
        public int Value;
    }

    private void DoStuff()
    {
        TreeNode Root = new TreeNode {Value = 0};
        for (var i = 1; i < 10; ++i)
        {
            TreeInsert(Root, new TreeNode {Value = i}, i);
        }
        PreOrder(Root, 0);
    }

    private void TreeInsert(TreeNode root, TreeNode item, int node)
    {
        int parent = (node - 1)/2;
        if (parent == 0)
        {
            if (root.Left == null)
                root.Left = item;
            else
                root.Right = item;
        }
        else
        {
            TreeNode child = ((parent%2) == 1) ? root.Left : root.Right;
            TreeInsert(child, item, parent);
        }
    }

    private void PreOrder(TreeNode root, int level)
    {
        if (root == null) return;
        Console.WriteLine("{0}{1}", new String('-', 2*level), root.Value);
        PreOrder(root.Left, level+1);
        PreOrder(root.Right, level + 1);
    }

Answer 2

Thanks to Jim's c# code and his solution. Below is the java version if anybody would like to try java.

    class BTnode 
{
    BTnode left;
    BTnode right;
    int data;

    BTnode(int data) {
        this.data = data;
    }
    /**Best way to implement it*/
    void insert(BTnode root, BTnode newnode,int num){
        if (root == null) return;
        else{
            int parent = (num-1)/2;
            if( parent==0 ){
                if (root.left == null)
                    root.left = newnode;
                else 
                    root.right = newnode;
            }
            else {
                root = ((parent%2)==1) ? root.left:root.right; // correct path
                insert(root,newnode,parent);
            }
        }
    }
    //PRINT using bfs
    void bfs(BTnode root){
        LinkedList<BTnode> ls = new LinkedList<BTnode>();
        LinkedList<BTnode> ls1 = new LinkedList<BTnode>();
        LinkedList<BTnode> t;
        ls.addLast(root);
        while (ls.size() != 0) {
            t = ls;
            ls = ls1;
            ls1 = t;  // swap two list to get one level of all the children
            while(ls1.size()!=0) {
                BTnode temp = ls1.poll();
                System.out.print(temp.data+" ");
                if(temp.left != null) 
                    ls.addLast(temp.left);
                if(temp.right != null) 
                    ls.addLast(temp.right);
            }
            System.out.println();
        }
    }
} 

Answer 3

Know I am late but the above answers have bugs that make them incomplete binary trees. Finding the correct path requires going all the way to the ancestor closest to the root rather than just looking at the parent. I changed the function quite a lot though and included info on parent in a node to illustrate.

class CompleteTree {
    Node root;

public CompleteTree() {
    root = null;
    } 

void insertWrapper(int value) {
    if (root == null) root = new Node(value);
        else insert(root,new Node(value));
    }

void insert(Node root, Node newnode) {
    if (((newnode.value - 1) / 2) == root.value) {
       if (root.left == null) {
            newnode.parent = root;              
            root.left = newnode;
       }
       else {
            newnode.parent = root;
            root.right = newnode;
       }
    }
    else {
       //goal to get ancestor 1 level under root to base the decision which subtree to go next
       int ancestor = parent;
       while (((ancestor - 1) / 2) > root.value) {
           ancestor = (ancestor - 1) / 2;
       }
       root = ((ancestor%2)==1) ? root.left : root.right;
       insert(root,newnode);
    }
    }


void printInorder(Node root) {
    if (root == null) return;
    printInorder(root.left);
    System.out.print("Hi, i am "+root.value+" and my parent is ");
    if (root.parent == null) System.out.println ("NULL");
        else System.out.println(root.parent.value);
    printInorder(root.right);
    }
}

class Node {
    int value;
    Node left;
    Node right;
    Node parent;

public Node (int value) {
    this.value = value;
    left = null;
    right = null;
    parent = null;
    }

public Node (int value, Node parent) {
    this.value = value;
    left = null;
    right = null;
    this.parent = parent;
    }
}

Test:

public static void main (String[] args) throws java.lang.Exception
{
    CompleteTree b = new CompleteTree();
    for (int i=0; i<10; i++) {
        b.insertWrapper(i);
    }
    b.printInorder(b.root);
}

I think the above answers failed insertion starting with no 9.

Answer 4

class Tree {
    Node root = null;
    int count = 0, temp2 = 0;

    public void insertData(int i) {
        count++;
        temp2 = count;

        root=createNode(root, i);

    }
/*
 * Here in this method I am trying to figure out at each step whether to select the left node or right node to insert the data.
 */
    private Node createNode(Node root2, int i) {

        if (root2 == null) {
            root2 = new Node(i);
        } else {

            int k = 0, temp = 0;
            for (int j = 0; j < temp2; j++) {
                temp = (int) (temp + Math.pow(2, j));
                k = j;
                if (temp2 - temp <= 0) {
                    temp = (int) (temp - Math.pow(2, j));
                    break;
                }

            }

            if (temp2 - temp <= Math.pow(2, k) / 2) {
                temp = 1;
                for (int j = 1; j < k; j++) {
                    temp = (int) (temp + Math.pow(2, j) / 2);
                }
                temp2 = temp2 - temp;
                root2.setLeft(createNode(root2.getLeft(), i));
            } else {
                temp = 1;
                for (int j = 1; j <= k; j++) {
                    temp = (int) (temp + Math.pow(2, j) / 2);
                }
                temp2 = temp2 - temp;

                root2.setRight(createNode(root2.getRight(), i));
            }

        }

        return root2;
    }

    public void printInorder()
    {
    printInorder(root);     
    }

    public void printInorder(Node node)
    {
        if (node == null)
            return;

        /* first recur on left child */
        printInorder(node.left);

        /* then print the data of node */
        System.out.print(node.data + " ");

        /* now recur on right child */
        printInorder(node.right);
    }

    private class Node {
        Node left;
        Node right;
        int data;

        Node(int i) {
            data = i;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }
    }

}

public class BinaryTree {
    public static void main(String[] args) {

        Tree t = new Tree();
        t.insertData(1);
        t.insertData(2);
        t.insertData(3);
        t.insertData(4);
        t.insertData(5);
        t.insertData(6);
        t.insertData(7);
        t.insertData(8);
        t.insertData(9);
        t.insertData(10);
        t.insertData(11);
        t.insertData(12);
        t.insertData(13);
        t.insertData(14);

    t.printInorder();

    }
}

Answer 5

//Node---
public class BinaryTreeNode<T> {
    private T data;
    private BinaryTreeNode<T> leftNode;
    private BinaryTreeNode<T> rightNode;

public BinaryTreeNode(T data) {
    this.data = data;
    this.leftNode = null;
    this.rightNode = null;
}

public T getData() {
    return data;
}

public void setData(T data) {
    this.data = data;
}

public BinaryTreeNode<T> getLeftNode() {
    return leftNode;
}

public void setLeftNode(BinaryTreeNode<T> leftNode) {
    this.leftNode = leftNode;
}

public BinaryTreeNode<T> getRightNode() {
    return rightNode;
}

public void setRightNode(BinaryTreeNode<T> rightNode) {
    this.rightNode = rightNode;
}
}

//Binary Tree---
public class BinaryTree<T> {
private BinaryTreeNode<T> rootNode;

public BinaryTreeNode<T> getRootNode() {
    return rootNode;
}

public void setRootNode(BinaryTreeNode<T> rootNode) {
    this.rootNode = rootNode;
}

public void insert(T data){
    this.setRootNode(insert(this.getRootNode(), data));
}

private BinaryTreeNode insert(BinaryTreeNode<T> node, T data){
    if(node == null){
        node = new BinaryTreeNode<>(data);
    }else{
        if(node.getLeftNode() == null){
            node.setLeftNode(insert(node.getLeftNode(), data));
        }else if(node.getRightNode() == null){
            node.setRightNode(insert(node.getRightNode(), data));
        } else{
            if(node.getLeftNode().getLeftNode() == null || node.getLeftNode().getRightNode() == null){
                insert(node.getLeftNode(), data);
            }else if(node.getRightNode().getLeftNode() == null || node.getRightNode().getRightNode() == null){
                insert(node.getRightNode(), data);
            }else{
                insert(node.getLeftNode(), data);
            }
        }
    }
    return node;
}
}