data structures - How to insert a node into a complete binary tree in Java? -

as know, when inserting complete binary tree have fill children leafs left right. have following method inserts node complete binary tree.

//fields private t item; private int size; private cbtree<t> left, right;  //add method public void add(t item)  {     if(left == null)     {         left = new cbtree<t>(item);         size += left.size;     }     else if(right == null)     {         right = new cbtree<t>(item);         size += right.size;     }     else if(!((left.left != null) && (left.right != null)) &&             ((right.left == null) || (right.right == null)))     {         left.add(item);     }     else     {         right.add(item);     } } 

the problem implementation after 11th node adds 12th node left child of 8 instead of 6. understand happening because following line reassigning root of tree left child of root.

left.add(item); 

so changing root 2. there way change root original value? trying accomplish without using stacks , queues.

it's not sufficient check children of children determine side go to, because tree reaches height 4 won't work more, since children of children of root won't change point forward yet can still go either left or right.

2 approaches come mind:

1. have complete variable @ each node.

   a node no children complete.

   a node 2 complete children of equal size complete.

   whenever update tree (insert or delete) update variable each affected node well.

2. mathematically determine whether subtree complete based on size.

   a tree of size 2^n - 1 complete (for n).

   note: work if we're not allowed freely delete elements without keeping tree complete.

for either approach, when doing insertion, go left (left.add(item)) if either of these conditions true:

• the left subtree not complete
• the left , right subtrees of same size (both complete, meaning we're increasing height insertion)

i'll leave implementation details you.

---

note: need update size when doing left.add(item); , right.add(item);. stick size++ in add function, since we're adding 1 element size increases 1 no matter what.