0

I am implementing a deletion of a node from a binary search tree in python. I got stuck in an edge case. Consider next code:

class Node():
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right
root = Node(5)
root.right = Node(10)

How to implement a function that deletes the root. I do not want the function return new root. In C++ I can modify pointer to make root point to its child, however in python variables are labels essentially. Is it even possible to do in python?

Community
  • 1
  • 1
ashim
  • 24,380
  • 29
  • 72
  • 96

1 Answers1

2

There is indeed no way to replace root and have it replaced wherever the instance pointed to by the name root appears.

The only way to achieve what you want is to mutate root to duplicate the child node.

def delete(node, inheritLeft=True):
    child = node.left if inheritLeft else node.right
    node.value = child.value
    node.left = child.left
    node.right = child.right

(Obviously you might want to do something smarter regarding choosing which node to inherit).

Gareth Latty
  • 86,389
  • 17
  • 178
  • 183
  • Good answer. What if there is only one root without children? – ashim May 09 '14 at 20:21
  • @msh That depends on what behaviour you want in your system. Maybe you want to set all the values to `None`, or have some other special flag for a null node. There is no way to replace the overall node with `None`, however, as you can only mutate, not replace the value and have your changes affect other names. – Gareth Latty May 09 '14 at 20:23
  • I just want to implement deletion in binary search tree http://en.wikipedia.org/wiki/Binary_search_tree#Deletion . In case when there is only one root, the algorithm does not do anything. – ashim May 09 '14 at 20:25
  • @msh In which case, you can just do nothing here. – Gareth Latty May 09 '14 at 20:27