Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Delete operation on binary search tree

  1. Jun 5, 2008 #1


    User Avatar
    Homework Helper

    The following diagram is from the section in my notes titled "Operations on Binary Search Trees". Specifically it explains via pseudocode how to implement a delete function for a BST:

    http://img410.imageshack.us/img410/4225/deletetreexz0.jpg [Broken]

    What I don't understand in the 2nd box is why "return T.left" is written. I thought the purpose of deleting a tree node in a BST would be to literally delete the object corresponding to the tree node. Instead the pseudocode appears to return the child node of the node to be deleted. Why is this done?
    Last edited by a moderator: May 3, 2017
  2. jcsd
  3. Jun 6, 2008 #2


    User Avatar
    Homework Helper

    This is not a delete function, and it doesn't include the case where an element has two children. It appears to be a sub-function that should be called by another function that isn't described.
    Last edited: Jun 6, 2008
  4. Jun 9, 2008 #3


    User Avatar
    Homework Helper

    Thanks for replying, Jeff. I did a search on Google and found the following:

    It turns out that deleting a BST node entails removing only that node itself and not its child sub-trees as I had thought it would. The child sub-trees of that node-to-be deleted would then be re-allocated in the BST. I've uploaded the portion of my notes which describe this operation in full. But it's strange that there isn't any delete keyword which I had expected, nor is there any pseudo-code which explains that deleting a node would require "re-pointing" the pointers of the parent tree-node of the node-to-be-deleted.

    Attached Files:

    Last edited by a moderator: Apr 23, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook