-
Notifications
You must be signed in to change notification settings - Fork 0
/
DeleteNode.py
113 lines (100 loc) · 2.66 KB
/
DeleteNode.py
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
'''
Created on Jan 10, 2016
@author: Rahul
'''
from Node import *
from copy import deepcopy
from numpy import Infinity
def find(root,data):
stack =[]
stack.append(root)
while stack:
n = stack.pop()
if n.val == data:
return n
else:
if n.left:
stack.append(n.left)
if n.right:
stack.append(n.right)
return None
def getParent(root,node):
if root == node:
return None
stack = []
stack.append(root)
while stack:
n = stack.pop()
if n.left == node:
return (n,"left")
if n.right == node:
return (n,"right")
if n.left:
stack.append(n.left)
if n.right:
stack.append(n.right)
return None
def getMin(root):
if root == None:
return None
stack = []
min1 = 1000
minnode = root
stack.append(root)
while stack:
n = stack.pop()
if n.val <= min1:
min1 = n.val
minnode = n
if n.left:
stack.append(n.left)
if n.right:
stack.append(n.right)
return minnode
def deleteNode(root,data):
if root == None:
return root
current = find(root,data)
if current:
#case 1:leaf
if current.left == None and current.right == None:
parent,pos = getParent(root,current)
if pos == "left":
parent.left = None
else:
parent.right= None
return root
#case 2
elif current.right == None:
parent,pos = getParent(root,current)
child = current.left
if pos == "left":
parent.left = child
else:
parent.right = child
return root
elif current.left == None:
parent,pos = getParent(root,current)
child = current.right
if pos == "left":
parent.left = child
else:
parent.right = child
return root
#case 3
else:
parent,pos = getParent(root,current)
minnode = getMin(current.right)
current.val = minnode.val
current.right = deleteNode(current.right,minnode.val)
return root
else:
return current
if __name__ == '__main__':
cb = CreateBinary()
root = cb.createTree()
root = deleteNode(root,23)
if not root:
print "element does not exist"
else:
print cb.inOrder(root)