Thread: Delete a node in a binary tree

  1. #1
    Registered User alice's Avatar
    Join Date
    Mar 2004
    Posts
    36

    Delete a node in a binary tree

    What the result will be if

    9,
    2,
    5

    is delete in the binary tree? (pls see the attach)

    for the case 5, will 6 be the upper node?

    thk a lot

  2. #2
    Registered User alice's Avatar
    Join Date
    Mar 2004
    Posts
    36
    Am I correct?
    pls see the attachment, thk

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    The result depends on the algorithm used for removal. After deleting 9 you can be reasonably sure that the resulting tree would be
    Code:
        5
       / \
      2   6
     /\    \
    1  4    7
      /    /
     3    8
    But for deleting 2, the result could be either
    Code:
      5
     / \
    1   6
     \   \
      4   7
     /   /
    3   8
         \
          9
    or
    Code:
        5
       / \
      3   6
     /\    \
    1  4    7
           /
          8
           \
            9
    The difference is which direction the replacing node is chosen from. Is it the predecessor or the successor? Deleting 5 will also have different results. Replacing the node with the successor would result in
    Code:
        6
       / \
      2   7
     /\  /
    1  4 8
      /   \
     3     9
    While replacing the node with the predecessor would give you
    Code:
        4
       / \
      2   6
     /\    \
    1  3    7
           /
          8
           \
            9
    Also remember that any removal from a binary search tree must result in a valid binary search tree. In other words, every node's value must be greater than the value in its left node and less than the value in its right node.

    This link might give you a little insight into the algorithms used. Two different methods are described.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree Delete Method
    By pobri19 in forum C# Programming
    Replies: 2
    Last Post: 09-26-2008, 09:43 AM
  2. Linked list probs
    By mouse163 in forum C++ Programming
    Replies: 5
    Last Post: 02-19-2005, 05:41 PM
  3. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 02:24 AM
  4. Dynamic list of Objects in External File
    By TechWins in forum C++ Programming
    Replies: 3
    Last Post: 12-18-2002, 02:05 PM
  5. binary tree node structure
    By Kirsten in forum C Programming
    Replies: 2
    Last Post: 04-26-2002, 08:02 PM