practice05.py

"""
Docstring for practice05:

Write a Python program to create a class representing a binary search tree. 
Include methods for inserting and searching for elements in the binary tree.

"""
# Define the Node class
class Node:
    def __init__(self, data): # Initialize the node with a value and optional left and right children
        self.data = data # Node value
        self.left = None   # Left child
        self.right = None  # Right child
    
    # String representation of the node for easier debugging
    def __str__(self):
        return f"Node({self.data})"
    
    def add_child(self, data):
        if data == self.data:
            return  # Duplicate values are not added in this BST implementation
        
        if data < self.data: # If data is less than current node's data
            # Insert data in the left subtree
            if self.left:
                self.left.add_child(data)
            # If left child doesn't exist, create a new node
            else:
                self.left = Node(data)
        else:
            # Insert data in the right subtree
            if self.right:
                self.right.add_child(data)
            # If right child doesn't exist, create a new node
            else:
                self.right = Node(data)
    
    def in_order_traversal(self):
        elements = []
        # Visit left subtree
        if self.left:
            elements += self.left.in_order_traversal()
        # Visit base node
        elements.append(self.data)
        # Visit right subtree
        if self.right:
            elements += self.right.in_order_traversal()
        return elements
    
    def pre_order_traversal(self):
        elements = []

        # Visit base node
        elements.append(self.data)
        # Visit left subtree
        if self.left:
            elements += self.left.pre_order_traversal()
        # Visit right subtree
        if self.right:
            elements += self.right.pre_order_traversal()
        return elements
    
    def post_order_traversal(self):
        elements = []
        # Visit left subtree
        if self.left:
            elements += self.left.post_order_traversal()
        # Visit right subtree
        if self.right:
            elements += self.right.post_order_traversal()
        # Visit base node
        elements.append(self.data)
        return elements
    
    def search(self, value):
        if self.data == value:
            return True
        
        if value < self.data:
            # Search in the left subtree
            if self.left:
                return self.left.search(value)
            else:
                return False

        if value > self.data:
            # Search in the right subtree
            if self.right:
                return self.right.search(value)
            else:
                return False

# build the binary search tree from a list of elements
def build_tree(elements):
    root = Node(elements[0]) # Create the root node
    for element in elements[1:]:
        root.add_child(element) # Insert each element into the BST
    return root

if __name__ == "__main__":
    elements = [17, 4, 1, 20, 9, 23, 18, 34]
    elements_tree = build_tree(elements)
    print("In-order Traversal of the BST:  ", elements_tree.in_order_traversal())
    print("Pre-order Traversal of the BST: ", elements_tree.pre_order_traversal())
    print("Post-order Traversal of the BST:", elements_tree.post_order_traversal())

    print("Search for 20 in the BST:", elements_tree.search(20)) # True
    print("Search for 5 in the BST: ", elements_tree.search(5))  # False