8000 Forgot to add the actual binary tree file · Aksh2020/complete-python-course@456c938 · GitHub
[go: up one dir, main page]
Skip to content

Commit 456c938

Browse files
jslvtrjslvtr
committed
Forgot to add the actual binary tree file
1 parent 83c9cdd commit 456c938

File tree

1 file changed

+100
-0
lines changed

1 file changed

+100
-0
lines changed

‎section17/projects/binary_tree/binary_tree.py

Lines changed: 100 additions & 0 deletions
< 5ADE tr class="diff-line-row">
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
from node import Node
2+
3+
4+
class BinaryTree:
5+
def __init__(self, head: Node):
6+
self.head = head
7+
8+
def add(self, new_node: Node):
9+
current_node = self.head
10+
while current_node:
11+
if new_node.value == current_node.value:
12+
raise ValueError('A node with that value already exists.')
13+
elif new_node.value < current_node.value:
14+
if current_node.left:
15+
current_node = current_node.left
16+
else:
17+
current_node.left = new_node
18+
break
19+
else:
20+
if current_node.right:
21+
current_node = current_node.right
22+
else:
23+
current_node.right = new_node
24+
break
25+
26+
def find(self, value: int):
27+
current_node = self.head
28+
while current_node:
29+
if value == current_node.value:
30+
return current_node
31+
elif value > current_node.value:
32+
current_node = current_node.right
33+
else:
34+
current_node = current_node.left
35+
raise LookupError(f'A node with value {value} was not found.')
36+
37+
def inorder(self):
38+
self._inorder_recursive(self.head)
39+
40+
def _inorder_recursive(self, current_node):
41+
if not current_node:
42+
return
43+
self._inorder_recursive(current_node.left)
44+
print(current_node)
45+
self._inorder_recursive(current_node.right)
46+
47+
def find_parent(self, value: int) -> Node:
48+
if self.head and self.head.value == value:
49+
return self.head
50+
51+
current_node = self.head
52+
while current_node:
53+
if (current_node.left and current_node.left.value == value) or\
54+
(current_node.right and current_node.right.value == value):
55+
return current_node
56+
elif value > current_node.value:
57+
current_node = current_node.right
58+
elif value < current_node.value:
59+
current_node = current_node.left
60+
61+
def find_rightmost(self, node: Node) -> Node:
62+
current_node = node
63+
while current_node.right:
64+
current_node = current_node.right
65+
return current_node
66+
67+
def delete(self, value: int):
68+
to_delete = self.find(value)
69+
to_delete_parent = self.find_parent(value)
70+
71+
if to_delete.left and to_delete.right:
72+
rightmost = self.find_rightmost(to_delete.left)
73+
rightmost_parent = self.find_parent(rightmost.value)
74+
75+
if rightmost_parent != to_delete:
76+
rightmost_parent.right = rightmost.left
77+
rightmost.left = to_delete.left
78+
rightmost.right = to_delete.right
79+
80+
if to_delete == to_delete_parent.left:
81+
to_delete_parent.left = rightmost
82+
elif to_delete == to_delete_parent.right:
83+
to_delete_parent.right = rightmost
84+
else:
85+
self.head = rightmost
86+
elif to_delete.left or to_delete.right:
87+
if to_delete == to_delete_parent.left:
88+
to_delete_parent.left = to_delete.right or to_delete.left
89+
elif to_delete == to_delete_parent.right:
90+
to_delete_parent.right = to_delete.right or to_delete.left
91+
else:
92+
self.head = to_delete.right or to_delete.left
93+
else:
94+
if to_delete == to_delete_parent.left:
95+
to_delete_parent.left = None
96+
elif to_delete == to_delete_parent.right:
97+
to_delete_parent.right = None
98+
else:
99+
self.head = None
100+

0 commit comments

Comments
 (0)
0