Deleting nodes from a tree in Python

Question

Below is a program I am working on that creates a tree and then can delete nodes from the tree. Im having trouble understanding just how deleting a node works and am looking for a bit of guidance. Currently My code replaces the node with the left most leaf, but Im trying to get it to delete the whole thing like it was never there. This is the area I am running into confusion with. Can someone explain?

    def remove(self, data):
        if self.root and self.root.data == data:  # special case for removing the root
            self.root = self.root.delete()
            return
        else:  # general case, removing a child node of some parent
            parent = self.root
            while parent:
                if data < parent.data:
                    child = parent.left
                    if child and child.data == data:
                        if child.left == None and child.right == None:
                            parent.left = None
                            return
                        if child.left == None:
                            parent.left = child.right
                            child = None
                            return
                        if child.right == None:
                            parent.left = child.left
                            child = None
                            return
                        left_most = child
                        while left_most.left != None:
                            second_left = left_most
                            left_most = left_most.left
                        child.data = left_most.data
                        second_left = None
                        return
                    parent = child
                else:
                    child = parent.right
                    if child and child.data == data:
                        if child.left == None and child.right == None:
                            parent.right = None
                            return
                        if child.left == None:
                            parent.right = child.right
                            child = None
                            return
                        if child.right == None:
                            parent.right = child.left
                            child = None
                            return
                        left_most = child
                        while left_most.left != None:
                            second_left = left_most
                            left_most = left_most.left
                        child.data = left_most.data
                        second_left = None
                        return
                    parent = child

Could you provide some sample input and show us the comparison between the actual output you get and the expected output you want? — JacobIRR
– JacobIRR, Commented May 2, 2017 at 3:15
What type of tree is this? AVR Binary Search? min_heap? max_heap? — Menachem Hornbacher
– Menachem Hornbacher, Commented May 2, 2017 at 3:18
I added a sample input and output. Hopefully it explains it a little better. — alienmode
– alienmode, Commented May 2, 2017 at 3:35
What do you expect the 11 to be replaced by? Do you want it to delete the whole subtree rooted there (so that 21 would have no nodes on the left)? Or do you expect it to preserve the order of the elements (in which case you need 11's right sub-tree's leftmost value or the left sub-tree's rightmost value. — Blckknght
– Blckknght, Commented May 2, 2017 at 3:47
I am looking for a way to make it remake the whole tree without the deleted node, so it would be preserving all the other input numbers like the deleted one was never there. — alienmode
– alienmode, Commented May 2, 2017 at 3:52

user3353877 · Accepted Answer · 2017-05-05 13:49:47Z

1

The homework assignment this question comes from links to a webpage that shows how the deletion is to be performed. Maybe you should post the entire assignment so that you can get your question answered.

answered May 5, 2017 at 13:49

user3353877

133 bronze badges

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

Collectives™ on Stack Overflow

Deleting nodes from a tree in Python

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related