Python: Binary Search Tree - BST

Introduction

This tutorial will guide you through the process of creating a Binary Search Tree (BST) in Python 3. You'll learn how to implement key functionalities like inserting nodes, finding values, and traversing the tree using preorder, postorder, and inorder methods. This foundational knowledge is essential for understanding more complex data structures and algorithms in computer science.

Step 1: Setting Up the Binary Search Tree Class

Begin by defining a class for the BST and a Node class that represents each node in the tree.

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

class BST:
    def __init__(self):
        self.root = None

Practical Advice

• Ensure that your Node class initializes with properties for left and right child nodes, as well as the node's value.
• The BST class should initialize with a root node set to None.

Step 2: Implementing the Insert Function

Create a method to insert new values into the BST.

def insert(self, root, key):
    if root is None:
        return Node(key)
    else:
        if key < root.val:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)
    return root

Practical Advice

• The method should recursively find the correct position for the new key in the tree.
• Remember to return the root node after insertion to maintain the tree structure.

Step 3: Implementing the Find Function

Develop a function to search for values within the BST.

def find(self, root, key):
    if root is None or root.val == key:
        return root
    if key < root.val:
        return self.find(root.left, key)
    return self.find(root.right, key)

Practical Advice

• This function uses recursion to navigate the tree.
• It should return the node if found or None if the key is not present.

Step 4: Implementing Traversal Methods

Create methods for preorder, inorder, and postorder traversal.

Preorder Traversal

def preorder(self, root):
    if root:
        print(root.val)
        self.preorder(root.left)
        self.preorder(root.right)

Inorder Traversal

def inorder(self, root):
    if root:
        self.inorder(root.left)
        print(root.val)
        self.inorder(root.right)

Postorder Traversal

def postorder(self, root):
    if root:
        self.postorder(root.left)
        self.postorder(root.right)
        print(root.val)

Practical Advice

• Each traversal method follows a specific order for visiting nodes.
• Print statements are used here for demonstration; consider returning values in a real application.

Step 5: Testing the BST Implementation

Incorporate a main function to test your BST implementation.

if __name__ == "__main__":
    bst = BST()
    bst.root = bst.insert(bst.root, 50)
    bst.insert(bst.root, 30)
    bst.insert(bst.root, 20)
    bst.insert(bst.root, 40)
    bst.insert(bst.root, 70)
    bst.insert(bst.root, 60)
    bst.insert(bst.root, 80)

    print("Preorder traversal:")
    bst.preorder(bst.root)

    print("Inorder traversal:")
    bst.inorder(bst.root)
    
    print("Postorder traversal:")
    bst.postorder(bst.root)

    found_node = bst.find(bst.root, 40)
    if found_node:
        print(f"Found node with value: {found_node.val}")
    else:
        print("Node not found.")

Practical Advice

• This test allows you to verify that your BST is working correctly by checking insertions and traversals.
• Adjust the values as needed to test different scenarios.

Conclusion

You've now built a basic Binary Search Tree in Python, complete with insertion, search, and traversal functions. This foundational data structure is crucial for many algorithms and applications. As next steps, consider exploring additional functionalities like removing nodes or balancing the tree. You can also expand your knowledge by checking out related videos or exploring the code on GitHub.