Jump to content
  • Advertisement
Sign in to follow this  
Alpha_ProgDes

adding a node to a Binary Tree from left to right

This topic is 4512 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
I foresee a complication if the subtrees have equal length.

Here is an idea I'll throw out.


// assume node is a pointer type

void 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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!