Inserting nodes into a tree Breadth First

Question

I am trying to generate tree with a breadth first form of insertion. I have tried to do this by generating a List with all the elements in the Tree in breadth first order. Then in my insertNode method I check if the node needs children with a method called needsChildren(), and if it does I add the node i am inserting into the tree in the leftmost spot possible.

if I call insertNode(10) insertNode(8) insertNode(20) insertNode(5) insertNode(29) insertNode(50)

The tree generated should be

          10
    8           20

5      29    50

and so on...

This solution is not working and I am not quite sure why. I think it is possible that my generateList is not working properly, but I have checked the last list printed and it seems to be right.

Is there a better way to do this, or is there a problem in my code that I can't find. Any help is really appreciated.

This is my TreeNode Class:

private static class TreeNode<T> {

    public T data;
    public TreeNode<T> left;
    public TreeNode<T> right;

    public TreeNode(T d) {
                    data = d;
                    left = null;
                    right = null;
    }
}

My insertNode method:

public void insertNode(T d) { 

    if(root==null){
        root= new TreeNode<T>(d);             
    }

    genList(root);

    if(needsChildren(nodesThatNeedChildren.get(0))){
        if(nodesThatNeedChildren.get(0).left==null){
            nodesThatNeedChildren.get(0).left= new TreeNode<T>(d);
        }else{
            nodesThatNeedChildren.get(0).right= new TreeNode<T>(d);
        }
    }else{
        while(!needsChildren(nodesThatNeedChildren.get(0))){
            nodesThatNeedChildren.remove(0);

        }
        System.out.println(nodesThatNeedChildren.get(0).data);


        if(nodesThatNeedChildren.get(0).left==null){
            nodesThatNeedChildren.get(0).left = new TreeNode<T>(d);
        }else{
            nodesThatNeedChildren.get(0).right = new TreeNode<T>(d);
        }
    }


}

My method to check if the node needs children:

public boolean needsChildren(TreeNode<T> node){
    if(node.left==null || node.right ==null){
        return true;
    }
    return false;
}

And my method that generates the list of all nodes in the tree:

public void genList(TreeNode<T> root) {
    //generate new List each time
    nodesThatNeedChildren.clear();
    nodesThatNeedChildren.add(root);

    //generate new Queue each time genList is called
    tempQueue.clear();
    tempQueue.add(root);

    while(!tempQueue.isEmpty()){

        TreeNode<T> node = tempQueue.remove(0);

        if(node.left != null){ 
            tempQueue.add(node.left);
            nodesThatNeedChildren.add(node.left);
        }     

        if(node.right != null){
            tempQueue.add(node.right);
            nodesThatNeedChildren.add(node.right);
        }
    }
}

Answer 1

I managed to find my mistake after a little bit of debugging. This issue was in my insertNode() method.

I was generating the firstNode I inserted twice into the tree.

this because I called

if(root==null){
    root= new TreeNode<T>(d);             
}

for the first node, but then did not break out of the method after instead the rest of the code was then called which was generating the first node twice. A simple else if statement solved the problem. The resolved code looks like this.

public void insertNode(T d) { 


    if(root==null){
        root= new TreeNode<T>(d); 
        size+=1;    

    }
    else if(root!=null){
        genList(root);
        if(needsChildren(nodesThatNeedChildren.get(0))){
            if(nodesThatNeedChildren.get(0).left==null){
                nodesThatNeedChildren.get(0).left= new TreeNode<T>(d);
                size+=1;
            }else{
                nodesThatNeedChildren.get(0).right= new TreeNode<T>(d);
                size+=1;
            }
        }else{
            while(!needsChildren(nodesThatNeedChildren.get(0))){
                nodesThatNeedChildren.remove(0);

            }

            if(nodesThatNeedChildren.get(0).left==null){
                nodesThatNeedChildren.get(0).left = new TreeNode<T>(d);
                size+=1;
            }else{
                nodesThatNeedChildren.get(0).right = new TreeNode<T>(d);
                size+=1;
            }
        }
    }




}