Breadth-first tree

Question

I seem to be having issues structuring a breadth-first tree.

In the code below, I have a node that is inserted through a loop in another class.

The structure of the tree is supposed to be as so:

    A
   / \
  B   C
 /\   /\
D E  F  G

Now for the code:

My code structures the left side correctly, whereas the right side adds the left side as well. I understand where in the code this happens, but is there a way to prevent this from happening?

public Node familyTree;

public void breadthFirst(Node newNode){
    familyTree = breadthFirst(familyTree,newNode);

}

public Node breadthFirst(Node T, Node newNode){
    if(T == null){
        T = newNode;
        return T;            
    }
    if(T.left == null){
        newNode.height = T.height + 1;            
        T.left = newNode;
        return T;
    }
    else if(T.right == null){
        newNode.height = T.height + 1;    
        T.right = newNode;
        return T;
    }
    else{            
         T.left = breadthFirst(T.left, newNode);
         T.right = breadthFirst(T.right, newNode); <-- this is the corporate           
    }
    return T;

}

You're thinking recursively. You should think iteratively. When doing breadth-first, work with a queue of 'yet-to-be-assessed' nodes. — Dibbeke, Nov 13 '16 at 01:13
You are doing a depthFirstSearch implementation, if you want to do breathFirstSearch, use a queue. — Hendrik T, Nov 13 '16 at 02:18

score 1 · Answer 1 · answered Nov 13 '16 at 02:28

if you are using recursive, definitely the implementation is a "depth-first-search", for breadth-first-search, you use a queue or a FIFO data structure

pseudo-code

public Node breadthFirst(Node T, Node searchNode){
  Queue queue = new Queue();
  queue.queue(T);

  while (!queue.isEmpty()) {
    Node curNode = queue.dequeue();
    if (curNode == null) continue;

    if (curNode.value().equals(searchNode.value()) {
      return curNode;
    }

    queue.queue(curNode.left);
    queue.queue(curNode.right);
  } 

  return null; //or throw exception not found
}

score 0 · Answer 2 · answered Nov 13 '16 at 01:27

I think a breadth-first tree resemble a complete binary tree, so you can employ Array to store it rather than link list. And about complete binary tree if the parent number is n then the left number=2*n+1 right=2*n+2.

for example: use array nodes[the amount of node] and the 0th Node is A(number begin zero) when the number n of Node is even like C(n=2) then nodes[(n-2)/2].right = nth node else odd like B then nodes[(n-1)/2].left = nth node

score 0 · Answer 3 · edited May 23 '17 at 12:01

What you are missing is using the height of the left and right node to determine which side the new node should be a child of when you reach the else statement. Currently, you're adding it to both sides regardless of where the node should be placed.

As an aside, it looks like you might be keeping track of depth of the tree in height attribute, rather than the height. This stackoverflow post does a good job of explaining the difference.

Breadth-first tree

3 Answers3