Binary Search Trees 🎯

Welcome to our deep dive into Binary Search Trees (BST)! This lesson is perfect for both beginners and intermediates. Let's get started!

Understanding Binary Search Trees 📝

A Binary Search Tree (BST) is a type of binary tree in which each node has at most two children - the left child and the right child. The tree follows the BST property, which means the key of the left subtree is less than the key of the root, and the key of the right subtree is greater than the key of the root.

Key Concepts 💡

Node: The basic building block of a BST, containing a key and two pointers for the left and right children.
Root: The topmost node of the BST.
Leaf: A node without any children.
Parent: The node that contains the edge connecting a child node.
Inorder Traversal: A method to visit all nodes in a BST in sorted order.

Creating a Basic BST 📝

Let's create a simple BST and understand how it works!

python

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

root = Node(5)
root.left = Node(3)
root.right = Node(7)
root.left.left = Node(2)
root.left.right = Node(4)

💡 Pro Tip: In this example, we created a simple BST with 5, 3, 7, 2, and 4. The key of the root node (5) is greater than the key of its left child (3) and less than the key of its right child (7).

BST Operations 💡

There are three main operations in a BST:

Insertion: Adding a new node to the tree.
Search: Finding a node with a specific key.
Deletion: Removing a node from the tree.

Insertion 📝

python

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

💡 Pro Tip: In the insert function, we recursively traverse the tree to find the appropriate place for the new node.

Search 📝

python

def search(root, key):
    if root is None or root.key == key:
        return root
    elif root.key < key:
        return search(root.right, key)
    else:
        return search(root.left, key)

💡 Pro Tip: In the search function, we traverse the tree recursively until we find the node with the desired key or reach the end of the tree.

Inorder Traversal 📝

Inorder traversal visits the left subtree, then the root, and finally the right subtree. This results in visiting the nodes in sorted order.

python

def inorder(root):
    if root:
        inorder(root.left)
        print(root.key, end=" ")
        inorder(root.right)

💡 Pro Tip: Inorder traversal is useful for sorting the keys of a BST in ascending order.

BST Quiz 📝

Deletion 💡

Deleting a node from a BST can be a complex process, but there are several strategies to handle it, such as the Inorder Successor and the Delete with Two Children methods. We'll cover these in a future lesson!

That's it for our Binary Search Trees tutorial! We hope you found it helpful and easy to understand. Happy coding! 🚀