Reputation: 277
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);
}
}
}
Upvotes: 1
Views: 1524
Reputation: 277
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;
}
}
}
}
Upvotes: 1