Thread: Binary tree addition

  1. #1
    Registered User
    Join Date
    Sep 2002

    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? ).

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    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:
     /   \
    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:
     /   \
    3     9
    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 )
    My best code is written with the delete key.

  3. #3
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :-

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM