Thread: 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:

Code:

               |
               a
             /   \

do I add the next node to the top of a or one of the bottom bits ( better word? ).
Thanks

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:

Code:

   5
 /   \
3     9

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:

Code:

   5
 /   \
3     9
 \
  4

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:

Code:

add_node ( node, new_node )
begin
  if node == NULL
    node = new_node
  else if new_node.value < node.value
    add_node ( node.left, new_node )
  else
    add_node ( node.right, new_node )
end

-Prelude

this will help u understand adding nodes and deleting nodes from binary trees.