DSA 47: Binary Search Trees - Traverse [Part 10]

1. TreeNode, Binary Tree & insert_node: Setup

Introduced previously.

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)
    

2. traverse

Steps:

• Call(traverse) on node’s left child until no left child, then print node.
• Call(traverse) on node’s right child until no right child, then print node.

Base-Case:

• (child) node does not exist, return None

def traverse_rec(root_node: TreeNode):
    current_node= root_node
    if not current_node:
        return
    traverse_rec(current_node.left)
    print(current_node.data)
    traverse_rec(current_node.right)
#              50
#       25           75
#    10     33     56     89  
root = TreeNode(50)
create_tree_from_root_node(root,node_list=[50,25,75,10,33,56,89])
traverse_rec(root) # expected 10,25,33,50,56,75,89

10
25
33
50
56
75
89

#             50
#      25           75
#  10     33     56     89  
# 4  11 30  40 52  61 82  95  
root = TreeNode(50)
create_tree_from_root_node(root)
traverse_rec(root) # expected 4,10,11,25,30,33,40,50,52,56,61,75,82,89,95

4
10
11
25
30
33
40
50
52
56
61
75
82
89
95

# binary search tree goals from scratch:
# 1. search_node
# 2. insert_node
# 3. insert_node_list
# 4. delete_node
# 5. traverse