DSA 42: Binary Search Trees - Alternative Approaches [Part 5]

1. Create TreeNode class: Setup

Previously introduced.

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

2. Create BinaryTree: Setup

By connecting individual TreeNodes.

Previously introduced.

# create a basic tree
#             50
#      25           75
#  10     33     56     89  
# 4  11 30  40 52  61 82  95  

def create_custom_binary_tree()->TreeNode:
    # Level: L4
    node04 = TreeNode( 4, left=None, right=None)
    node11 = TreeNode(11, left=None, right=None)
    node30 = TreeNode(30, left=None, right=None)
    node40 = TreeNode(40, left=None, right=None)
    # Level: R4
    node52 = TreeNode(52, left=None, right=None)
    node61 = TreeNode(61, left=None, right=None)
    node82 = TreeNode(82, left=None, right=None)
    node95 = TreeNode(95, left=None, right=None)

    # Level: L3
    node10 = TreeNode(10, left=node04, right=node11)
    node33 = TreeNode(33, left=node30, right=node40)
    # Level: R3
    node56 = TreeNode(56, left=node52, right=node61)
    node89 = TreeNode(89, left=node82, right=node95)

    # Level: L2
    node25 = TreeNode(25, left=node10, right=node33)
    # Level: R2
    node75 = TreeNode(75, left=node56, right=node89)

    # Level: L1
    root_node = node50 = TreeNode(50, left=node25, right=node75)
    return root_node

3. search_node

3.1 search_node: Recursive Approach

def search_node_recursive(root_node: TreeNode, target: int):
    current_node = root_node
    if target == current_node.data:
        print(f"Target Found! tgt{target}|node{current_node.data} ")
        return   
    if target < current_node.data: # go left
        if current_node.left:
            current_node=current_node.left
            return search_node_recursive(current_node, target)
        else:
            print(f"Target Not Found! tgt{target}|node{current_node.data} has no left-child ")
            return current_node
    else:
        if current_node.right:
            current_node=current_node.right
            return search_node_recursive(current_node, target)
        else:
            print(f"Target Not Found! tgt{target}|node{current_node.data} has no right-child ")
            return current_node

3.2 search_node: Iterative Approach

def search_node_iterative(root_node: TreeNode, target: int):
    current_node = root_node
    
    while current_node:
        if target == current_node.data:
            print(f"Target Found! tgt{target}|node{current_node.data} ")
            return   
        if target < current_node.data: # go left
            if current_node.left:
                current_node=current_node.left
                # return search_node_while(current_node, target)
            else:
                print(f"Target Not Found! tgt{target}|node{current_node.data} has no left-child ")
                return current_node
        else:
            if current_node.right:
                current_node=current_node.right
                # return search_node_while(current_node, target)
            else:
                print(f"Target Not Found! tgt{target}|node{current_node.data} has no right-child ")
                return current_node

3.3 search_node: Testing Both Approaches

# create a basic tree
#             50
#      25           75
#  10     33     56     89  
# 4  11 30  40 52  61 82  95  

root = create_custom_binary_tree()

search_node_recursive(root, 61)
search_node_iterative(root, 61)

print()
print()
search_node_recursive(root, 3)
search_node_iterative(root, 3)

Target Found! tgt61|node61 
Target Found! tgt61|node61 


Target Not Found! tgt3|node4 has no left-child 
Target Not Found! tgt3|node4 has no left-child 

<__main__.TreeNode at 0x7fbaf855f9d0>

4. insert_node

4.1 insert_node: Recursive Approach

def insert_node_recursion(root_node:TreeNode, target: int):
    current_node = root_node
    if target==current_node.data:
        print(f"Duplicate! Can't insert! value{target}|node{current_node.data}")
        return current_node
    # search 
    if target<current_node.data: # go left
        if current_node.left:
            current_node=current_node.left
            return insert_node_recursion(current_node,target)
        else: # insert
            current_node.left = TreeNode(target)
            print(f"Inserted target{target} as left-child of node{current_node.data} successfully!")
            return current_node.left
    else:
        if current_node.right: # go right
            current_node=current_node.right
            return insert_node_recursion(current_node,target)
        else: # insert
            current_node.right = TreeNode(target)
            print(f"Inserted target{target} as right-child of node{current_node.data} successfully!")
            return current_node.right

4.2 insert_node: Iterative Approach

def insert_node_iterative(root_node: TreeNode, target: int):
    current_node = root_node
    
    while current_node:
        if target == current_node.data:
            print(f"Duplicate! Can't insert! value{target}|node{current_node.data}")
            return current_node
        if target < current_node.data: # go left
            if current_node.left:
                current_node=current_node.left
                # return insert_node_while(current_node, target)
            else: # INSERT LEFT
                current_node.left = TreeNode(target)
                print(f"Inserted target{target} as left-child of node{current_node.data} successfully!")
                return current_node.left
        else:
            if current_node.right:
                current_node=current_node.right
                # return insert_node_while(current_node, target)
            else: # INSERT RIGHT
                current_node.right = TreeNode(target)
                print(f"Inserted target{target} as right-child of node{current_node.data} successfully!")
                return current_node.right

4.3 insert_node: Testing Both Approaches

#             50            # create a basic tree
#      25           75
#  10     33     56     89  
# 4  11 30  40 52  61 82  95  
root = create_custom_binary_tree()
insert_node_recursion(root, 12)
insert_node_recursion(root, 12)

print()
print()
root = create_custom_binary_tree()
insert_node_iterative(root, 12)
insert_node_iterative(root, 12)

Inserted target12 as right-child of node11 successfully!
Duplicate! Can't insert! value12|node12


Inserted target12 as right-child of node11 successfully!
Duplicate! Can't insert! value12|node12

<__main__.TreeNode at 0x7fbaf8363190>