Delete Node in a BST LeetCode solution in Python

1
# Definition for a binary tree node.
2
# class TreeNode:
3
#     def __init__(self, val=0, left=None, right=None):
4
#         self.val = val
5
#         self.left = left
6
#         self.right = right
7
class Solution:
8
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
9

10
def find_inorder(root, key):
11

12
	if root is None :
13
		return []
14

15
	return find_inorder(root.left, key) + [root.val] + find_inorder(root.right, key)
16

17
def find_preorder(root, key):
18

19
	if root is None:
20
		return []
21

22
	return [root.val] + find_preorder(root.left,key) + find_preorder(root.right, key)
23

24
preorder = find_preorder(root, key)
25

26
try:
27
	preorder.remove(key)
28
except:
29
	return root
30

31
inorder = find_inorder(root, key)
32

33
inorder.remove(key)
34

35

36

37

38
hashmap = {}
39

40
for i in range(len(inorder)):
41
	key = inorder[i]
42
	hashmap[key] = i
43

44
def buildTree(left, right):
45

46
	if left > right:
47
		return 
48

49
	val = inorder[left]
50
	root = TreeNode(val)
51

52
	index = hashmap[val]
53

54
	root.left = buildTree(left, index-1)
55
	root.right = buildTree(index+1, right)
56

57
	return root
58

59
N = len(inorder)
60
new_tree = buildTree(0,N-1)
61

62
return new_tree
63

64