FilesExpand file tree

 master

/

deleteNode.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

32 lines (29 loc) · 1.04 KB

 master

/

deleteNode.py

Copy path

Top

File metadata and controls

• Code
• Blame

32 lines (29 loc) · 1.04 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

"""

case 1: if node we want to delete has no children: simply delete it

case 2: if it has only one child, then replace it with its child

case 3: if it has two children, first find the inorder successor (or predecessor),

then replace the node's value with successor's value, and finally delete this successor

"""

def deleteNode(self, root, key):

if not root: return None

if key < root.val:

root.left = self.deleteNode(root.left, key)

elif key > root.val:

root.right = self.deleteNode(root.right, key)

else:

# if this node has only one child or no child:

if not root.left:

temp = root.right

root = None

return temp

elif not root.right:

temp = root.left

root = None

return temp

# otherwise, find the inorder successor:

curr = root.right

while curr.left:

curr = curr.left

root.val = curr.val

root.right = self.deleteNode(root.right, curr.val)

return root