class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def insert_node(root_node: TreeNode, target: int):
current_node = root_node
if target == current_node.data:
print(f"t[{target}]|c[{current_node.data}]: \t\tCannot insert duplicates")
return
if target < current_node.data: # left
if current_node.left: # go left-child: if exists
print(f"t[{target}]|c[{current_node.data}]: \t\tCurrent[{current_node.data}] has ONE left-child : GO LEFT[{current_node.left.data}]")
current_node=current_node.left
return insert_node(current_node, target)
else: # insert left-child: if not exist
current_node.left = TreeNode(target)
print(f"t[{target}]|c[{current_node.data}]: \t\tCurrent[{current_node.data}] has NO left-child: INSERTED LEFT CurrentLeft[{current_node.left.data}]")
return current_node.left
else:
if current_node.right: # go right-child: if exists
print(f"t[{target}]|c[{current_node.data}]: \t\tCurrent[{current_node.data}] has ONE right-child : GO right[{current_node.right.data}]")
current_node=current_node.right
return insert_node(current_node, target)
else: # insert right-child: if not exist
current_node.right = TreeNode(target)
print(f"t[{target}]|c[{current_node.data}]: \t\tCurrent[{current_node.data}] has NO right-child: INSERTED right Currentright[{current_node.right.data}]")
pass
def insert_node_clean(root_node: TreeNode, target: int):
current_node = root_node
if target == current_node.data:
return
if target < current_node.data: # left
if current_node.left: # go left-child: if exists
current_node=current_node.left
return insert_node_clean(current_node, target)
else: # insert left-child: if not exist
current_node.left = TreeNode(target)
return current_node.left
else:
if current_node.right: # go right-child: if exists
current_node=current_node.right
return insert_node_clean(current_node, target)
else: # insert right-child: if not exist
current_node.right = TreeNode(target)
pass
# create a basic tree
# 50
# 25 75
# 10 33 56 89
# 4 11 30 40 52 61 82 95
def insert_node_list(root_node:TreeNode, node_list: list[int], show_outputs:bool=True):
for node in node_list:
if show_outputs:
insert_node(root_node, node)
else:
insert_node_clean(root_node, node)
def create_tree_from_root_node(root_node = TreeNode(50),node_list=[25,75,10,33,56,89,4,11,30,40,52,61,82,95]):
insert_node_list(root_node, node_list,show_outputs=False)
1. TreeNode, Binary Tree & insert_node: Setup
Introduced previously.
2. Confirm Tree
# 50
# 25 75
# 10 33 56 89
# 4 11 30 40 52 61 82 95
root = TreeNode(50)
create_tree_from_root_node(root)
print(f"[L1] root.data: \t\t\t[{root.data}] (expected: 50)")
print()
print(f"[L2] root.left.data: \t\t\t[{root.left.data}] (expected: 25)")
print(f"[L2] root.right.data: \t\t\t[{root.right.data}] (expected: 75)")
print()
print(f"[L3] root.left.left.data: \t\t[{root.left.left.data}] (expected: 10)")
print(f"[L3] root.left.right.data: \t\t[{root.left.right.data}] (expected: 33)")
print(f"[L3] root.right.left.data: \t\t[{root.right.left.data}] (expected: 56)")
print(f"[L3] root.right.right.data: \t\t[{root.right.right.data}] (expected: 89)")
print()
print(f"[L4] root.left.left.left.data: \t\t[{root.left.left.left.data}] (expected: 4)")
print(f"[L4] root.left.left.right.data: \t[{root.left.left.right.data}] (expected: 11)")
print(f"[L4] root.left.right.left.data: \t[{root.left.right.left.data}] (expected: 30)")
print(f"[L4] root.left.right.right.data: \t[{root.left.right.right.data}] (expected: 40)")
print()
print(f"[L4] root.right.left.left.data: \t[{root.right.left.left.data}] (expected: 52)")
print(f"[L4] root.right.left.right.data: \t[{root.right.left.right.data}] (expected: 61)")
print(f"[L4] root.right.right.left.data: \t[{root.right.right.left.data}] (expected: 82)")
print(f"[L4] root.right.right.right.data:\t[{root.right.right.right.data}] (expected: 95)")[L1] root.data: [50] (expected: 50)
[L2] root.left.data: [25] (expected: 25)
[L2] root.right.data: [75] (expected: 75)
[L3] root.left.left.data: [10] (expected: 10)
[L3] root.left.right.data: [33] (expected: 33)
[L3] root.right.left.data: [56] (expected: 56)
[L3] root.right.right.data: [89] (expected: 89)
[L4] root.left.left.left.data: [4] (expected: 4)
[L4] root.left.left.right.data: [11] (expected: 11)
[L4] root.left.right.left.data: [30] (expected: 30)
[L4] root.left.right.right.data: [40] (expected: 40)
[L4] root.right.left.left.data: [52] (expected: 52)
[L4] root.right.left.right.data: [61] (expected: 61)
[L4] root.right.right.left.data: [82] (expected: 82)
[L4] root.right.right.right.data: [95] (expected: 95)3. find_successor_node
def find_successor_node(target_node: TreeNode):
successor_node = target_node.right # go right
print(f"t{target_node.data}.tr[{successor_node.data}]: go right...{successor_node.data}")
if not successor_node.left:
# [75] to succeed [50]
if successor_node.right:
print(f"s{successor_node.data} has no left kids: s will t[{target_node.data}], t.right -> s.right[{successor_node.right.data}]")
target_node.data = successor_node.data # no need to update targets parents because only replacing data not nodes
target_node.right = successor_node.right
else:
target_node.data = successor_node.data
print(f"s{successor_node.data} has no left kids: s will succeed t[{target_node.data}], t.right -> s.right[{None}]")
pass
while successor_node.left:
print(f"s{successor_node.data}.l[{successor_node.left.data}]: s has a left_child, go left...")
parent_node = successor_node
successor_node = successor_node.left
print(f"s{successor_node.data}: s no further left_childs, check is s has a right_child...")
# successor_node is not left_most child
# 1. has no_right_child: no further action
# i. parent_left = None instead of parent_left = s_node (removing s_node to replace target_node)
# ii target.data = s_node.data
if not successor_node.right:
print(f"s{successor_node.data}: s has 0 right_child...p[{parent_node.data}] from p.left[{parent_node.left.data}] -> p.left[{None}]")
parent_node.left = None
if successor_node.right:
print(f"s{successor_node.data}: s has 1 right_child...p[{parent_node.data}] from p.left[{parent_node.left.data}] -> s[{successor_node.data}].right[{successor_node.right.data}]")
# print(f"s{successor_node.data}: succesor has 1 right_child...parent.left -> successors.right[{successor_node.right.data}]")
parent_node.left = successor_node.right
# 2. has snode has_right_child
# i. parent_left = snode_right_child
# ii target.data = s_node.data
print(f"s{successor_node.data} to succeed t[{target_node.data}]")
target_node.data = successor_node.data
return successor_node
# NO RIGHT CHILD
# [t50]
# 25 [s75]
# NO RIGHT CHILD
# [s75]
# 25 []
# RIGHT CHILD
# [t50]
# 25 [s75]
# [sc80]
# RIGHT CHILD
# [s75]
# 25 [sc80]
# [scc81]4. delete_node
def delete_node(root_node: TreeNode, target: int):
current_node = root_node
parent_node = None
target_node = None
while current_node:
if target == current_node.data:
target_node = current_node
print(f"t{target}==c{current_node.data}: target found! [Determine Children Count]...")
break
elif target < current_node.data: # go left
print(f"t{target}<-c{current_node.data}: go left...")
parent_node = current_node
current_node = current_node.left
else: # go right
print(f"t{target}->c{current_node.data}: go right...")
parent_node = current_node
current_node = current_node.right
if not target_node:
print(f"t{target}!=p{parent_node.data}: target not found because node has no more children!")
return
if target_node.left and target_node.right:
print(f"t{target}.lr[{target_node.left.data},{target_node.right.data}]: target has two kids! [Find Successor Node]...")
s_node = find_successor_node(target_node)
return
else: # 0 or 1 kid
targets_child = (target_node.left or target_node.right)
print(f"t[{target}]: target has 0 or 1 children! [Find Successor Node]...")
if not parent_node: # root node has no parents: replace parent (and its kids) with child (and its kids)
print(f"t{target}.tc[{targets_child.data}]:tc[{targets_child.data}] succeeds t[{target}], no parents ptrs to update")
target_node.data = targets_child.data
target_node.left = targets_child.left
target_node.right = targets_child.right
elif parent_node.left == target_node:
if targets_child:
print(f"t{target}.tc[{targets_child.data}]:tc[{targets_child.data}] succeeds t[{target}], p[{parent_node.data}]l[{parent_node.left.data}] updated to point to tc[{targets_child.data}]")
parent_node.left = targets_child
print(f"t{target}.tc[{targets_child.data}]:final result p[{parent_node.data}]l[{parent_node.left.data}]")
else:
print(f"t{target} has no kids: {target} deleted, parent_node.left pointing to [None]")
parent_node.left = targets_child
return
elif parent_node.right == target_node:
if targets_child:
print(f"t{target}.tc[{targets_child.data}]:tc[{targets_child.data}] succeeds t[{target}], p[{parent_node.data}]r[{parent_node.right.data}] updated to point to tc[{targets_child.data}]")
parent_node.right = targets_child
print(f"t{target}.tc[{targets_child.data}]:final result p[{parent_node.data}]r[{parent_node.right.data}]")
else:
print(f"t{target} has no kids: {target} deleted, parent_node.right pointing to [None]")
parent_node.right = targets_child
return
return
# 50
# 25 75
# 10 33 56 89
# 4 11 30 40 52 61 82 95
root = None
root = TreeNode(50)
create_tree_from_root_node(root)
delete_node(root, 50)
# delete_node(root, 10)t50==c50: target found! [Determine Children Count]...
t50.lr[25,75]: target has two kids! [Find Successor Node]...
t50.tr[75]: go right...75
s75.l[56]: s has a left_child, go left...
s56.l[52]: s has a left_child, go left...
s52: s no further left_childs, check is s has a right_child...
s52: s has 0 right_child...p[56] from p.left[52] -> p.left[None]
s52 to succeed t[50]root = None
root = TreeNode(50)
create_tree_from_root_node(root, node_list=[25])
delete_node(root,50)
root.datat50==c50: target found! [Determine Children Count]...
t[50]: target has 0 or 1 children! [Find Successor Node]...
t50.tc[25]:tc[25] succeeds t[50], no parents ptrs to update25root = None
root = TreeNode(50)
create_tree_from_root_node(root, node_list=[25,10])
delete_node(root,25)t25<-c50: go left...
t25==c25: target found! [Determine Children Count]...
t[25]: target has 0 or 1 children! [Find Successor Node]...
t25.tc[10]:tc[10] succeeds t[25], p[50]l[25] updated to point to tc[10]
t25.tc[10]:final result p[50]l[10]root = None
root = TreeNode(50)
create_tree_from_root_node(root, node_list=[51,52])
delete_node(root,51)t51->c50: go right...
t51==c51: target found! [Determine Children Count]...
t[51]: target has 0 or 1 children! [Find Successor Node]...
t51.tc[52]:tc[52] succeeds t[51], p[50]r[51] updated to point to tc[52]
t51.tc[52]:final result p[50]r[52]root = None
root = TreeNode(50)
create_tree_from_root_node(root)
delete_node(root, 4)t4<-c50: go left...
t4<-c25: go left...
t4<-c10: go left...
t4==c4: target found! [Determine Children Count]...
t[4]: target has 0 or 1 children! [Find Successor Node]...
t4 has no kids: 4 deleted, parent_node.left pointing to [None]root = None
root = TreeNode(50)
create_tree_from_root_node(root, node_list=[25,75])
delete_node(root,75)
# NO RIGHT CHILD
# [t50]
# 25 [s75]
# NO RIGHT CHILD
# [s75]
# 25 []t75->c50: go right...
t75==c75: target found! [Determine Children Count]...
t[75]: target has 0 or 1 children! [Find Successor Node]...
t75 has no kids: 75 deleted, parent_node.right pointing to [None]
# RIGHT CHILD
# [t50]
# 25 [s75]
# [sc80]
# RIGHT CHILD
# [s75]
# 25 [sc80]
# [scc81]# [50]X
# 25 [75]
# 10 33 [56] 89
# 4 11 30 40 [52] 61 82 95
root = None
root = TreeNode(50)
create_tree_from_root_node(root)
delete_node(root, 50)
# [52]
# 25 [75]
# 10 33 [56] 89
# 4 11 30 40 [] 61 82 95
print(root.data) # expected 52
print(root.right.left.data) # expected 56
print(root.right.left.left.data) # expected errort50==c50: target found! [Determine Children Count]...
t50.lr[25,75]: target has two kids! [Find Successor Node]...
t50.tr[75]: go right...75
s75.l[56]: s has a left_child, go left...
s56.l[52]: s has a left_child, go left...
s52: s no further left_childs, check is s has a right_child...
s52: s has 0 right_child...p[56] from p.left[52] -> p.left[None]
s52 to succeed t[50]
52
56--------------------------------------------------------------------------- AttributeError Traceback (most recent call last) Cell In[20], line 18 16 print(root.data) # expected 52 17 print(root.right.left.data) # expected 56 ---> 18 print(root.right.left.left.data) # expected error AttributeError: 'NoneType' object has no attribute 'data'
# [50]X
# 25 [75]
# 10 33 [56] 89
# 4 11 30 40 [52] 61 82 95
# [55]
root = None
root = TreeNode(50)
create_tree_from_root_node(root)
insert_node(root, 55)
delete_node(root, 50)
root.right.left.left.data # expected 55
# [52]
# 25 [75]
# 10 33 [56] 89
# 4 11 30 40 [55] 61 82 95
# []t[55]|c[50]: Current[50] has ONE right-child : GO right[75]
t[55]|c[75]: Current[75] has ONE left-child : GO LEFT[56]
t[55]|c[56]: Current[56] has ONE left-child : GO LEFT[52]
t[55]|c[52]: Current[52] has NO right-child: INSERTED right Currentright[55]
t50==c50: target found! [Determine Children Count]...
t50.lr[25,75]: target has two kids! [Find Successor Node]...
t50.tr[75]: go right...75
s75.l[56]: s has a left_child, go left...
s56.l[52]: s has a left_child, go left...
s52: s no further left_childs, check is s has a right_child...
s52: s has 1 right_child...p[56] from p.left[52] -> s[52].right[55]
s52 to succeed t[50]55