# adding a node to a Binary Tree from left to right

## Recommended Posts

Alpha_ProgDes    6936
now I'm talking about plain ol' Binary Trees, not Binary Search/Sort Trees. I wanted to know (without using arrays as my base) if there is a way to add a node and have it insert and fill the tree from left to right. I've gotten as far as a 2-level depth but afterwards I get stuck. It just keeps adding nodes to the left. Any suggestions or is this an impossibility without using one of the speciality binary trees?

##### Share on other sites
SiCrane    11839
I have no idea what you just asked.

##### Share on other sites
Alpha_ProgDes    6936
Ok... let me try again.

In my binary tree, I want to add a node and have it automatically populate the tree from left to right. Then go down a level, again add itself to the tree from left to right.
so...
       a                      a   /   \                  /    b      c   then         b     c                        /                       d

and so forth.

Clearer?

##### Share on other sites
SiCrane    11839
Ok. Give your tree an extra bit of information: each node keeps track of the minimum depth of each of its sub trees. If a node has no subtrees its depth is 0. If it has two subtrees its depth is min(depth(left), depth(right)). Can you see how you could use that information to decide where to add the next node?

##### Share on other sites
Alpha_ProgDes    6936
ok... so checkDepth(), if a node has a depth of 0, add a left node. then checkDepth() again, if depth != 0 add a right node.

i take it, this will be a recursive task.

##### Share on other sites
SiCrane    11839
Not really. That would cause you to create a tree where you build on the right with only one left node along the spine. Think of depth as a balancing factor. Also, it can be done iteratively.

##### Share on other sites
Alpha_ProgDes    6936
It seems like the grasshopper will be in the temple a little longer than intended.

##### Share on other sites
Boder    938
I foresee a complication if the subtrees have equal length.

Here is an idea I'll throw out.

// assume node is a pointer typevoid add(node tree, node newbie) { list<node> nodelist int depth = 1 list.pushback(tree)  while( !add_node (nodelist, newbie, depth) );}bool add_node (list&, node, depth&) { for i from 0 to depth:   temp = list.popfront()   if either temp.child == null:      that temp.child = node      return true   else      list.pushback(temp.leftchild)      list.pushback(temp.rightchild)   depth = depth*2}

Basically scan down the tree one level at a time, keeping track of all the nodes on a horizontal level, and adding the node to the first null encountered from left to right.

##### Share on other sites
SiCrane    11839
No, there are no complications if the two subtrees have equal depth. Draw out a tree where the two subtrees have equal depth that has been created by this type of algorithm. Do you see where the node would go?

##### Share on other sites
Alpha_ProgDes    6936
I'm not gonna lie to you... I don't get the code you just posted.

##### Share on other sites
Boder    938
I see a problem finding out how to increment the mindepth counter on each node, because if the two subtrees are equal in length, then the depth counter should not change. If they are unequal we increment the depth counter.

##### Share on other sites
SiCrane    11839
Oops, depth should be min(depth(left), depth(right)) + 1, and 0 if there are no sub trees. Make more sense now?

##### Share on other sites
Boder    938
Let's pretend you are the recursive function.

I pass you the current node and the node to add. You see that:
curr.depth = 8
curr.left.depth = 8
curr.right.depth = 7

Do you increment the minimum depth counter?

##### Share on other sites
SiCrane    11839
You would add the node to the appropriate subtree. Doing so would give you sufficient information as to whether or not the increment the depth or not.

##### Share on other sites
iMalc    2466
Quote:
 Original post by Alpha_ProgDesnow I'm talking about plain ol' Binary Trees, not Binary Search/Sort Trees. I wanted to know (without using arrays as my base) if there is a way to add a node and have it insert and fill the tree from left to right.
You can do the same thing that would happen when using an array, but actually use a binary tree.
All you need to do is keep track of the current number of items in the tree, which you probably do anyway. Then with that number, each bit tells you whether you go left or right during insertion.
e.g. A tree with 5 items:
      A  B       CD   E
First increment the count. This gives us 6. 6 is 110 in binary. Now 0 means go left, 1 means go right. Ignore the most significant digit, and start from the next most significant bit, proceeding towards the lest significant bit.
So you go right, then insert on the left.

Now that you have 6 items, add 1 to that and get 7. 7 is 111 in binary. So you go right, then insert on the right.
Now you have 7 items. +1 gives 8. 8 = 1000. So you go left twice and insert on the left. etc...

No need for recursion, or storing data in each node, or any inefficient algorithm.[cool]

##### Share on other sites
Boder    938

How can I become leet like you iMalc?

##### Share on other sites
iMalc    2466
I was just thinking that it is so easy for a heap to do exactly this with no extra storage, so there has to be a way to do it with a tree. Then I just got lucky I suppose.

##### Share on other sites
Alpha_ProgDes    6936
Quote:
Original post by iMalc
Quote:
 Original post by Alpha_ProgDesnow I'm talking about plain ol' Binary Trees, not Binary Search/Sort Trees. I wanted to know (without using arrays as my base) if there is a way to add a node and have it insert and fill the tree from left to right.
You can do the same thing that would happen when using an array, but actually use a binary tree.
All you need to do is keep track of the current number of items in the tree, which you probably do anyway. Then with that number, each bit tells you whether you go left or right during insertion.
e.g. A tree with 5 items:
      A  B       CD   E
First increment the count. This gives us 6. 6 is 110 in binary. Now 0 means go left, 1 means go right. Ignore the most significant digit, and start from the next most significant bit, proceeding towards the lest significant bit.
So you go right, then insert on the left.

Now that you have 6 items, add 1 to that and get 7. 7 is 111 in binary. So you go right, then insert on the right.
Now you have 7 items. +1 gives 8. 8 = 1000. So you go left twice and insert on the left. etc...

No need for recursion, or storing data in each node, or any inefficient algorithm.[cool]

Dude!!! That's #@\$%ing genius!!! You sir are a genius.
Now I'm still trying to figure out the mindepth thing.

##### Share on other sites
Alpha_ProgDes    6936
yeah uh that minimum depth algorithm .... my brain hits wall.

##### Share on other sites
Boder    938
If you use iMalc's algorithm, then you don't need to keep track of mindepth.

But here is how I understood the insert if you keep track of mindepth.
// untested!// returns mindepthint insert(node Node, node NewNode) {  if (Node.left = NULL)    Node.left = NewNode;    return 0;  else if (Node.right == NULL)    Node.right = NewNode;    return 1;  if (Node.left.mindepth <= Node.right.mindepth)    Node.mindepth = min ( Node.right.mindepth, insert(Node.left, NewNode) );  else    Node.mindepth = min ( Node.left.mindepth, insert(Node.right, NewNode) );  return Node.mindepth;}

##### Share on other sites
WhardieJones    100
Add one variable to keep track of the last node. From here you can find the node to the right or left pretty easily. The other option is to thread your nodes but this is extra data dependent on N, but also constant time.

I had to do this when I was implementing a binary heap. It's not very hard.

##### Share on other sites
Alpha_ProgDes    6936
I came up with a (not-so) novel idea.
Each node holds the count of the nodes under it plus itself
so for example if a is the root and we add nodes: b and c.
a would have a count of 3 and b = 1, c = 1 and depth = 1.

now if i have a complete and balanced binary tree of 15 nodes. i know that the root's left and right subtree have 2^(depth)-1 nodes. so i do something like this:
nodePtr = rootwhile (node != 0)   if (nodePtr.left.count != 2^(depth)-1 || nodePtr.left.full && nodePtr.right.full)      //move pointer down to the left node   else      //move pointer down to the right node

that should do it! granted this hit me right before i went to sleep.
hopefully that should work for me. thanks siCrane, boder, and iMalc [smile]

am pretty sure, this i can make this recursive as well (as you can see, i'm trying to get that down as well)

##### Share on other sites
Krumble    151
Why not just use arrays as your base and add your node to the end of the array? You can then use the following formulas for children and parents:

If your current node is i, then:

parent: (i-1)/2 (integer division)
left child: 2*(i+1)-1
right child: 2*(i+1)

##### Share on other sites
Timkin    864
Quote:
 Original post by iMalcAll you need to do is keep track of the current number of items in the tree, which you probably do anyway. Then with that number, each bit tells you whether you go left or right during insertion.

Hehe... this is actually the basis of the common implementation of the discrete fast fourier transform algorithm! Any number can be assigned a position in a binary tree simply from the bit sequence in its base-2 representation. ;) If you didn't already know this iMalc, then kudos to you for picking up on it. 8)

Cheers,

Timkin

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account