3

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?

2
  • Your structure is a little odd but if that is really what you want then isn't else { addToTree(tree.getLeft(), name } all you need? Nov 3, 2012 at 22:53
  • Well, you'd need to save it into a variable, as it returns a BinaryTree, but even if you did that, the right side gets neglected completely.
    – Doug Smith
    Nov 3, 2012 at 23:08

5 Answers 5

2

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)
1
  • It doesn't return anything, it just adds a new node to the tree. If you want to return the root element, you can simply return it. Nov 6, 2012 at 8:01
0

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
        }
    }
}
3
  • What does this return? How does it affect the root?
    – Doug Smith
    Nov 4, 2012 at 1:38
  • The algorithm simply adds a child to the parent, It doesn't return anything. Nov 4, 2012 at 1:55
  • Well, with my code I'm code trying to return the resulting Binary Tree that had the new addition added to it. With yours, is it not just attaching the addition to a sub-tree that was given from the queue, and then not doing anything with it? How would I have it return it?
    – Doug Smith
    Nov 4, 2012 at 2:19
0

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.

0

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.

3
  • This won't work, as it neglects the right side completely. Sketch the output, it will result in a tree that scales downward to the left.
    – Doug Smith
    Nov 3, 2012 at 23:45
  • @Doug - It will produce exactly what you have asked for. I have clearly stated that I do not believe it is what you want. Nov 3, 2012 at 23:52
  • No, you didn't, I said for instance. As in that's one example of. It violates pretty much every other situation that could occur from what I said.
    – Doug Smith
    Nov 4, 2012 at 1:26
0

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.)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.