BST Search and Insertion

1. Representing a BST Node in Python

Before we can search or insert, we need a way to represent the tree itself. Since a tree is a collection of connected nodes, we'll start by defining a class for a single node. Each node needs to store its own value and have pointers (or references) to its left and right children.

A straightforward way to structure this in Python is as follows:

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

This simple class is the building block for our entire tree. The __init__ method initializes a new node with a given value and sets its children to None. We can then connect these nodes to form a tree structure. An empty tree can be represented by a root that is None.

2. The Search Operation

The search operation in a BST is a beautiful demonstration of the "divide and conquer" principle. The process is inherently recursive.

The Logic:

1. Start at the root of the tree.
2. Compare the value you're searching for with the current node's value.
   • If they are equal, you've found the value. Return True.
   • If the target value is less than the current node's value, you know it can only be in the left subtree. Recursively search the left child.
   • If the target value is greater than the current node's value, it must be in the right subtree. Recursively search the right child.
3. If you reach a point where the current node is None, it means you've followed the correct path to where the value should be, but it's not there. The search has failed, so return False.

Now, let's look at how to translate this logic into code. The following article provides a clean, recursive implementation.

To see this logic explained with animations and a code walkthrough, let's watch a segment of the video from LucidProgramming.

3. The Insertion Operation

The logic for insertion is closely related to searching. To insert a new value, you first search for it to find the correct position. The place where the search would fail (i.e., where you'd hit a None pointer) is precisely where the new node should be attached.

The Logic:

1. Start at the root. If the tree is empty, the new node becomes the root.
2. Compare the value to be inserted with the current node's value.
   • If the new value is the same as the current node's value, we do nothing to avoid duplicates.
   • If the new value is less than the current node's value, we move to the left child. If the left child is None, we insert the new node here. Otherwise, we recursively call insert on the left child.
   • If the new value is greater than the current node's value, we move to the right child. If the right child is None, we insert the new node here. Otherwise, we recursively call insert on the right child.

Let's turn to our resources for the implementation.

Now, let's watch a video walkthrough of the implementation. The speaker's explanation of the recursive calls is particularly helpful.

4. Putting It All Together

Now that we have the search and insert methods, let's see how to use them to build a tree from a list of numbers and then query it. This is a very common task in competitive programming.

The codebasics video demonstrates how to build a tree from a list of elements and then test the search functionality.

Here's the complete BSTNode class with the methods we've just learned, structured similarly to the Boot.dev article. You can run this code yourself to experiment.

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

    def insert(self, val):
        # If the node is empty, this becomes the root node
        if not self.val:
            self.val = val
            return

        # Ignore duplicate values
        if self.val == val:
            return

        # If val is smaller, go to the left subtree
        if val < self.val:
            if self.left:
                self.left.insert(val)
            else:
                self.left = BSTNode(val)
        # If val is larger, go to the right subtree
        else:
            if self.right:
                self.right.insert(val)
            else:
                self.right = BSTNode(val)

    def exists(self, val):
        # Base case: value found
        if val == self.val:
            return True

        # Recursive step: search left subtree
        if val < self.val:
            if self.left is None:
                return False
            return self.left.exists(val)

        # Recursive step: search right subtree
        if self.right is None:
            return False
        return self.right.exists(val)

# --- How to use it ---
nums = [15, 10, 20, 8, 12, 18, 25]

# Create the root node with the first element
bst = BSTNode()
for num in nums:
    bst.insert(num)

# Test the search function
print("Does 12 exist?", bst.exists(12))  # Output: True
print("Does 99 exist?", bst.exists(99)) # Output: False

Conclusion

In this lesson, we transitioned from understanding the theory of BSTs to implementing their core functionalities. You have learned how to write recursive functions to efficiently search for and insert data while preserving the crucial ordering properties of the tree.

Key Takeaways:

• A BST can be represented in Python using a Node class with val, left, and right attributes.
• The search operation recursively follows a single path down the tree, guided by comparisons, resulting in $O(h)$ time complexity (where $h$ is the tree's height).
• The insertion operation works by first searching for the correct position and then adding the new node at the point where the search fails, also in $O(h)$ time.
• Both operations are elegant recursive algorithms that directly leverage the BST's defining properties.

Up Next:
While search and insertion are relatively straightforward, removing a node from a BST is more complex. You have to handle three different cases depending on whether the node to be deleted has zero, one, or two children. In our next lesson, we will tackle the logic and implementation for deleting a node from a BST.