Delete a root from a tree in python

Question

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?

I'm pretty confused what you're trying to do here ... Can you try to explain it better? — mgilson
– mgilson, Commented May 9, 2014 at 20:18
@Mephy I assume the OP has other references to root they also want updated. — Gareth Latty
– Gareth Latty, Commented May 9, 2014 at 20:19
What do you mean by "I do not want function to return new root" What do you want to happen to the reference to root after it is deleted? — deweyredman
– deweyredman, Commented May 9, 2014 at 20:19
@Mephy Yes, this will work. What if there is only one root, without children — ashim
– ashim, Commented May 9, 2014 at 20:20

Gareth Latty · Accepted Answer · 2014-05-09 20:19:44Z

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

answered May 9, 2014 at 20:19

Gareth Latty

89.4k18 gold badges183 silver badges187 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

ashim Over a year ago

Good answer. What if there is only one root without children?

Gareth Latty Over a year ago

@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.

ashim Over a year ago

I just want to implement deletion in binary search tree en.wikipedia.org/wiki/Binary_search_tree#Deletion . In case when there is only one root, the algorithm does not do anything.

Gareth Latty Over a year ago

@msh In which case, you can just do nothing here.

Collectives™ on Stack Overflow

Delete a root from a tree in python

1 Answer 1

4 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Linked

Related