Binary Search Tree: Insertion and Search

1. What is a Binary Search Tree?

A Binary Search Tree is a special type of tree data structure that makes searching for data highly efficient. It's called "binary" because each node can have at most two children, and it's a "search tree" because its structure is optimized for searching.

A BST must satisfy three key properties for every node in the tree:

1. All values in the node's left subtree are less than the node's own value.
2. All values in the node's right subtree are greater than the node's own value.
3. Both the left and right subtrees must also be binary search trees, meaning they follow these same rules.

As a convention, BSTs typically do not allow duplicate values.

To get a dynamic overview of what a BST is and why its ordering is so important, let's watch a short video.

2. Searching for a Value in a BST

The strict ordering of a BST makes searching incredibly fast. The process is similar to the binary search algorithm you might use on a sorted array. You start at the root and at each node, you make a simple decision:

1. Is the target value equal to the current node's value? If yes, you've found it!
2. Is the target value less than the current node's value? If yes, you only need to search in the left subtree.
3. Is the target value greater than the current node's value? If yes, you only need to search in the right subtree.

You repeat this process, effectively eliminating half of the remaining tree at each step. This is what gives the BST its power. While searching a list could take $O(n)$ time in the worst case (checking every element), searching a reasonably balanced BST takes $O(\log n)$ time, which is exponentially faster for large datasets.

3. Inserting a Value into a BST

The process for inserting a new value is very similar to searching. You follow the same logic to find where the new value should be.

1. Start at the root.
2. Compare the new value with the current node's value.
3. If the new value is less, move to the left child. If it's greater, move to the right child.
4. Continue this until you reach a spot where the child node is None. This empty spot is where you insert the new node, ensuring the BST properties are maintained.

The following short video segment will visualize this insertion process for you.

4. Python Implementation

Now, let's put this theory into practice by building a Binary Search Tree in Python. We will create a class to represent the nodes and their connections.

The implementation will be recursive. Recursion is a natural fit for tree structures because a tree is a recursive data structure itself (a tree is a root node with two smaller trees as children).

Step-by-Step Code

We'll follow the class-based approach demonstrated in the videos. First, we define a BinarySearchTreeNode class. This class will hold the data and have pointers to its left and right children. The insert and search logic will be methods within this class.

Here is the complete Python code for our BinarySearchTreeNode class, including methods for inserting and searching. I've also added a helper method in_order_traversal that returns the elements of the tree in sorted order, which is useful for verifying our tree is built correctly.

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

    def insert(self, data):
        """Inserts a new node with the given data. Duplicates are ignored."""
        if self.data == data:
            return # Ignore duplicates

        if data < self.data:
            # Add data in the left subtree
            if self.left:
                self.left.insert(data) # Recursively call insert on the left child
            else:
                self.left = BinarySearchTreeNode(data) # If no left child, create a new node
        else:
            # Add data in the right subtree
            if self.right:
                self.right.insert(data) # Recursively call insert on the right child
            else:
                self.right = BinarySearchTreeNode(data) # If no right child, create a new node

    def search(self, val):
        """Searches for a value in the tree. Returns True if found, False otherwise."""
        if self.data == val:
            return True # Value is found at the current node

        if val < self.data:
            # Value might be in the left subtree
            if self.left:
                return self.left.search(val) # Recursively search the left subtree
            else:
                return False # No left subtree, so value is not here
        else:
            # Value might be in the right subtree
            if self.right:
                return self.right.search(val) # Recursively search the right subtree
            else:
                return False # No right subtree, so value is not here

    def in_order_traversal(self):
        """Returns a list of elements in sorted order."""
        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

# Helper function to build a tree from a list of numbers
def build_tree(elements):
    if not elements:
        return None
    
    root = BinarySearchTreeNode(elements[0])
    for i in range(1, len(elements)):
        root.insert(elements[i])
    
    return root

# --- Let's test it out! ---
numbers = [15, 12, 7, 14, 27, 20, 88, 23]
number_tree = build_tree(numbers)

print("Tree elements in sorted order:", number_tree.in_order_traversal())

# Test the search method
print("Is 20 in the tree?", number_tree.search(20)) # Expected: True
print("Is 99 in the tree?", number_tree.search(99)) # Expected: False

Conclusion

Congratulations! You have now learned about the Binary Search Tree and implemented its most fundamental operations. This is a significant step into the world of non-linear data structures.

Key Takeaways:

• A Binary Search Tree (BST) organizes data hierarchically, with every node's left subtree containing smaller values and its right subtree containing larger values.
• This structure allows for efficient search and insertion operations, typically with a time complexity of $O(\log n)$ for a balanced tree.
• The logic for both search and insertion involves starting at the root and recursively traversing down the tree based on comparisons.
• In Python, a BST is commonly implemented with a Node class that contains the data and references to left and right child nodes.

Preview of the Next Lesson:

We've seen how to build and search a tree. But what if we want to visit every single node in a systematic way? In the next lesson, we will explore tree traversal algorithms. You will learn about inorder, preorder, and postorder traversals, which are essential for tasks like printing all tree elements, saving a tree to a file, or creating a copy of a tree.