Using the Breadth-first traversal algorithm, I'm adding items to a Binary Tree in consecutive order, but they're not adding properly

Question

I have the following method that I'm using (uses the Breadth-first traversal algorithm) to add items into a Binary Tree in consecutive order.

For instance, if I had

  A
 / \
 B  C
/  
D 

I would want the next addition to be:

  A
 / \
 B  C
/ \ 
D  E

My problem lies in the fact that I'm not sure how to return the value properly. I know that when we encounter the first null node, that's where we insert the value, but what do we insert it into? If we insert it into the Binary Tree we're getting from the queue, that's a sub-tree of the root (or the tree we're trying to add to) so returning that won't be the full tree.

Here's the code I have:

public static <T> BinaryTree<T> addToTree(BinaryTree<T> t1, BinaryTree<T> t2) {
    Queue<BinaryTree<T>> treeQueue = new LinkedList<BinaryTree<T>>();

    while (t1 != null) {
        if (t1.getLeft() == null) {
            t1.attachLeft(t2);
            break;
        }
        treeQueue.add(t1.getLeft());

        if (t1.getRight() == null) {
            t1.attachRight(t2);
            break;
        }
        treeQueue.add(t1.getRight());

        if (!treeQueue.isEmpty()) t1 = treeQueue.remove();
        else t1 = null;
    }
    return t1;
}

Answer 1

Ok, I think I now get what you are asking for.

Your breadth-first implementation is correct.

A binary tree is a sort of "self-contained" structure. You start with the root, called A, with two references to two other binary trees, "left" and "right"

You start from:

    A
   / \
  B  C
 /  
D 

and add a binary tree, E as right subtree of B:

  A
 / \
 B  C
/ \ 
D  E

Your implementation, as it is, returns a subtree, "B", which is where the new subtree has been appended. I am not sure what BinaryTree implementation you are using, but I expect the:

"B".attachRight("E");

to modify the original tree, so the "new" tree with the node appended is still the one starting with "A"- ie you do not have to return anything! I do not know if your implementation keeps track of the "parent", if yes you can traverse the parents hierarchy starting from "B" until you find a node where the parent is null - the root ("a" again)

The answer you want after calling addToTree(BinaryTree t1, BinaryTree t2) is "t1", the "A" rooted tree you passed as first argument.

Answer 2

Your problem is here:

if (!treeQueue.isEmpty()) t1 = treeQueue.remove(); else t1 = null;

If a node does not have children, you set its reference to null to interrupt the while but this is also the value your function returns. You can just use a temporary variable to store the reference to the node you want to return.