FilesExpand file tree

 master

/

delete_node.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

66 lines (54 loc) · 1.67 KB

 master

/

delete_node.py

Copy path

Top

File metadata and controls

• Code
• Blame

66 lines (54 loc) · 1.67 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

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

"""

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.

If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]

key = 3

5

/ \

3 6

/ \ \

2 4 7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

5

/ \

4 6

/ \

2 7

Another valid answer is [5,2,6,null,4,null,7].

5

/ \

2 6

\ \

4 7

"""

class Solution(object):

def deleteNode(self, root, key):

"""

:type root: TreeNode

:type key: int

:rtype: TreeNode

"""

if not root: return None

if root.val == key:

if root.left:

# Find the right most leaf of the left sub-tree

left_right_most = root.left

while left_right_most.right:

left_right_most = left_right_most.right

# Attach right child to the right of that leaf

left_right_most.right = root.right

# Return left child instead of root, a.k.a delete root

return root.left

else:

return root.right

# If left or right child got deleted, the returned root is the child of the deleted node.

elif root.val > key:

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

else:

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

return root