Binary tree addition
Hi, I'm having a little bit of trouble getting my head round the addition of a new node to a binary tree. Do you add a new node to the top or bottom of an existing node.
If I had this for example:
do I add the next node to the top of a or one of the bottom bits ( better word? ).
There is no top and bottom in a basic binary tree, only left and right. Let's say you have a tree with three values, 5, 9, and 3:
Now, you want to add the value 4 to the three, but 5 already has a left node. In this case you place 4 to the right of 3 because it has a greater value than 3, but a lower value than 5:
You can think of this insertion as placing 4 between 3 and 5. When adding to a basic binary tree, you test the value being inserted with every node until you can place it. If the value is greater than the node, move to the node's right, if the value is less than the node, move to the node's left. When you reach an empty node (usually NULL) this is where you insert the value. The recursive algorithm to do this is as follows:
add_node ( node, new_node )
if node == NULL
node = new_node
else if new_node.value < node.value
add_node ( node.left, new_node )
add_node ( node.right, new_node )