0

Implementation of the algorithm in Wiki article has a drawback. If the tree consists from only one root then nothing happen. The tree is not modified. How to fix this issue? In C++ it is possible to set root pointer to null, but what to do in python?

ashim
  • 24,380
  • 29
  • 72
  • 96
  • 1
    if the tree has only the root, then the root is a leaf, so you delete it. If you have an object with a reference to the root, you can set it to nothing. – Simon Bergot May 09 '14 at 20:33
  • A binary search tree will always only consist of one root. Do you mean if the BST only has one node remaining (aka the root)? Have you tried testing this code out and see if it leaves the root node? – But I'm Not A Wrapper Class May 09 '14 at 20:33
  • @Simon How do you delete it? – ashim May 09 '14 at 20:34
  • 2
    @msh How are empty trees represented in your code? Because that is the result: An empty tree – Niklas B. May 09 '14 at 20:36
  • 1
    Python has `None` if you are trying to perform something similar to `null` in c++ – Farmer Joe May 09 '14 at 20:36
  • @FarmerJoe @Simon, the problem is that you cannot do `root=None` inside a function. There will be no effect on outside `root`. – ashim May 09 '14 at 20:40
  • 1
    This is a continuation of a previous question, and the OP is looking to replace the value with `None`, but for *all* names that have that instance assigned to them - this is not possible in Python. – Gareth Latty May 09 '14 at 20:40
  • 1
    @Lattyware, that is useful info. – Hans Then May 09 '14 at 20:42
  • 1
    @msh In the future, you should really provide more information if you expect an answer specific to what you are doing. – Farmer Joe May 09 '14 at 20:48

1 Answers1

2

This is a continuation of a previous question, and the OP is looking to replace the value with None, but for all names that have that instance assigned to them - this is not possible in Python.

The answer is there is no way to delete the value in this case due to the way Python is designed - you would have to implement an object manager of some kind, store it in a container and access it through that, or change your design not to rely on mutation.

Another question worth asking - is this a case that is likely to happen? It may be possible (and desirable) just to define this as a limitation where the root node can't be destroyed. I can't think of a case where you would want that functionality.

Community
  • 1
  • 1
Gareth Latty
  • 86,389
  • 17
  • 178
  • 183