With Binary Trees, I want to add the next node in consecutive order, my algorithm isn't quite working however

Question

For instance, if I had

  A
 / \
 B  C
/  
D 

I would want the next addition to be:

  A
 / \
 B  C
/ \ 
D  E

But I'm having a lot of trouble detecting where the next spot for the item to input will be. I have the following code:

    public static BinaryTree<String> addToTree(BinaryTree<String> tree, String name) {
        if (tree.getLeft() == null) {
            BinaryTree<String> newTree = new BinaryTree<String>();
            newTree.makeRoot(name);
            tree.attachLeft(newTree);
        }
        else if (tree.getRight() == null) {
            BinaryTree<String> newTree = new BinaryTree<String>();
            newTree.makeRoot(name);
            tree.attachRight(newTree);
        }
        // Both are non-null
        else {
            if (tree.getLeft().getLeft() == null || tree.getLeft().getRight() == null) {
                tree.attachLeft(addToTree(tree.getLeft(), name));
            }
            else if (tree.getRight().getLeft() == null || tree.getRight().getRight() == null) {
                tree.attachRight(addToTree(tree.getRight(), name));
            }
        }

        return tree;
    }

But it will only work for up to a three level tree. If I try to add the fourth, it no longer adds any.

How do I implement it so it will figure out where the next item is null, and then add it there?

I also thought of having a checkNullity() method, wherein I'd take a tree, and check if its children were null, but I was also having trouble figuring out how to get the children's children. I wanted to find where it was null and then add it there.

Could anyone offer some input?

Answer 1

In order to add an element to a proper place in a binary tree, you have to go from the root at at each node answer the following question: Should I descend to the left or to the right subtree? This is what your problem boils down to - how to make this decision at each node.

You start is OK. If the node has no left subtree, then the newly added leaf should be its left child. And if the node has a left subtree but no right subtree, then the newly added leaf should be its right child.

But how to decide if the node has both subtrees? For this you'll need to keep some sort of information at the nodes that you can use to decide. One possibility is to keep at each node the total size of its subtree. Then if both subtrees have the same size, it means both are perfectly balanced and so you add to the left. Otherwise, if the left subtree has size 2^n-1 it means that it's balanced (and the right one is not) so you add to the right. If not, add to the left.

---

However, you can do much simpler than that. Since your trees always keep this structure, you can represent a tree as an ArrayList. The root node is at index 0 and for a node at index n its children are at indexes _2*n+1_ and _2*n+2_. This is just how binary heaps are implemented. This way, you'll get O(1) time complexity for adding a new node - simply append it at the end of the list. (However, if you need some classical tree operations like rotations, this implementation won't work.)

Answer 2

This certainly creates the tree you are asking for although I am still not sure it is what you want:

public class BinaryTree<T> {
  T root = null;
  BinaryTree<T> left = null;
  BinaryTree<T> right = null;

  public BinaryTree<T> getLeft() {
    return left;
  }

  public BinaryTree<T> getRight() {
    return right;
  }

  public void makeRoot(T root) {
    this.root = root;
  }

  public void attachLeft(BinaryTree<T> tree) {
    left = tree;
  }

  public void attachRight(BinaryTree<T> tree) {
    right = tree;
  }

  public static BinaryTree<String> addToTree(BinaryTree<String> tree, String name) {
    if (tree.getLeft() == null) {
      BinaryTree<String> newTree = new BinaryTree<String>();
      newTree.makeRoot(name);
      tree.attachLeft(newTree);
    } else if (tree.getRight() == null) {
      BinaryTree<String> newTree = new BinaryTree<String>();
      newTree.makeRoot(name);
      tree.attachRight(newTree);
    } else {
      addToTree(tree.getLeft(), name);
    }
    return tree;
  }

  public static void main(String[] args) {

    try {
      BinaryTree<String> tree = new BinaryTree<String>();
      String add = "ABCDEFG";
      tree.makeRoot(add.substring(0, 1));
      for (int i = 1; i < add.length(); i++) {
        addToTree(tree, add.substring(i, i + 1));
      }
      System.out.println("Done");
    } catch (Throwable e) {
      e.printStackTrace();
    }
  }
}

Added

I have clearly misunderstood the question. Perhaps an example will help.

If I added one character at a time (as strings) from the following string what would you expect?

"ABCDEFG"

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

or something else.

What would you then expect from

"ADEFGBC"

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

or

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

or something else?

Either is possible but I cannot see any value in either case.

Answer 3

You could enumerate all nodes while adding them to the tree. If you want to add the n-th node to the tree, it'll be a child of the n/2-th node: left if n%2 == 0 and right if n%2 == 1.

Answer 4

Since, you want to insert the element in the order from left to right and starting from the same level. I would suggest you to look in to Breath First Search. I have provided an basic implementation.

public void insert(child, root){

    if (root == null){
        root = child
    }

    Node iter = root
    Myqueue q = new Myqueue(); //Implementation of the Java Queue Interface

    while (iter!=null){

        //Check: If the left node exists, enque in the que
        if(iter.is_left()){
            q.insert(iter.left)
        }
        else{
            iter.left = child
            iter = null
        }

        //Similary for the right
        if(iter.is_right()){
            q.insert(iter.right)
        }
        else{
            iter.right = child
            iter = null
        }
        if (iter != null){
        iter = q.poll() //Retreiving the head of the queue
        }
    }
}

Answer 5

You can modify breadth first traversal to accomplish this I think. When you pop up the items from the queue, check if any of the children is empty. The first empty child slot is the place you want to add to.

addNode(root, newNode) 
  q = empty queue
  q.enqueue(root)
  while not q.empty do
    node := q.dequeue()
    if node.left == null
      //create new node as nodes left child
      return
    q.enqueue(node.left)
    if node.right == null
      //create new node as nodes right child
      return
    q.enqueue(node.right)