DSA 41: Binary Search Trees - Insertion [Part 4]

1. TreeNode

Introduced previously

class TreeNode:
    def __init__(self,data,left=None,right=None):
        self.data=data
        self.left=left
        self.right=right

2. insert

• If on the correct side (left if target less than current node else right) and
• the child node does not exist then insert,
  • otherwise go to child node and do the comparison again.

def insert(tree_node: TreeNode, value: int):
    current_node = tree_node
    if not current_node:
        print("cant insert empty node")
    if value<current_node.data:
        if not current_node.left:
            current_node.left=TreeNode(value)
        else:
            insert(current_node.left, value)
    else:
        if not current_node.right:
            current_node.right=TreeNode(value)
        else:
            insert(current_node.right, value)

3. Test It

root_node = TreeNode(50)
insert(root_node,30)
insert(root_node,70)
insert(root_node,20)
insert(root_node,40)
insert(root_node,60)
insert(root_node,80)
print(f"expected[50]: {root_node.data}") #50
print(f"expected[30]: {root_node.left.data}") #30
print(f"expected[70]: {root_node.right.data}") #70
print(f"expected[20]: {root_node.left.left.data}") #20
print(f"expected[40]: {root_node.left.right.data}") #40
print(f"expected[60]: {root_node.right.left.data}") #60
print(f"expected[80]: {root_node.right.left.data}") #80

expected[50]: 50
expected[30]: 30
expected[70]: 70
expected[20]: 20
expected[40]: 40
expected[60]: 60
expected[80]: 60