BST Practice: Finding the Minimum Value

The Core Logic: The Leftmost Node

The defining property of a Binary Search Tree is its inherent order:

• For any given node, all values in its left subtree are smaller.
• For any given node, all values in its right subtree are larger.

This rule provides a straightforward algorithm for finding the minimum value. To find the smallest possible value, we should always choose the smaller path. Therefore, starting from the root, we just need to follow the left child pointers until we can't go any further. The node we end up at—the one with no left child—must contain the minimum value in the entire tree.

This simple but powerful logic is the key.

This task is a common exercise when learning about BSTs. The following video sets it up as a challenge.

Now, let's explore how to turn this logic into code. We'll look at two common implementations: iterative and recursive.

Approach 1: The Iterative Solution

The most direct way to implement "keep going left" is with a simple loop. This is an iterative approach.

The algorithm is as follows:

1. Check if the tree is empty (i.e., the root is None). If so, there is no minimum value.
2. Start with a current pointer at the root node.
3. Use a while loop that continues as long as current.left is not None.
4. Inside the loop, move to the left: current = current.left.
5. When the loop finishes, current is pointing to the leftmost node. Return current.data.

This approach is efficient and easy to understand. Let's look at a clear Python implementation.

Complexity Analysis

• Time Complexity: The loop runs as many times as there are levels to traverse to reach the leftmost node. In the worst case, this is the height of the tree, $h$. So, the time complexity is $O(h)$. As we learned, this is $O(\log n)$ for a balanced tree and $O(n)$ for a skewed tree.
• Space Complexity: This approach is very memory-efficient. We only use one extra variable (current) to keep track of the node. The space used does not grow with the size of the tree. Therefore, the space complexity is $O(1)$, or constant space.

Approach 2: The Recursive Solution

Since a tree is a recursive data structure, we can also solve this problem using recursion. This often leads to elegant, though not always the most space-efficient, code.

The recursive logic is:

• Base Case: If the current node has no left child, then it is the minimum value in the subtree we're looking at. We've found our answer, so we return its value.
• Recursive Step: If the current node does have a left child, then we know the minimum value must be in that left subtree. So, we call the function again on the left child (find_min(node.left)).

The following video explains this recursive formulation clearly.

Here is what the same logic looks like in Python, as shown in the GeeksforGeeks article, which provides multiple approaches.

Complexity Analysis

• Time Complexity: Just like the iterative version, the number of recursive calls is equal to the height of the path to the leftmost node. The time complexity is $O(h)$.
• Space Complexity: Each recursive call adds a new frame to the call stack. In the worst case, the number of active calls at one time is equal to the height of the tree, $h$. Therefore, the space complexity is $O(h)$. This is less space-efficient than the iterative solution's $O(1)$ space.

Practice Exercise

Now it's your turn to write the code. Below is the BinarySearchTreeNode class we have been working with. Your task is to add two methods to it: find_min() and find_max().

1. Copy the code into a Python file (e.g., bst_min_max.py).
2. Implement the find_min() method using the iterative approach we discussed.
3. Implement the find_max() method. The logic is symmetrical to finding the minimum—you just need to go right instead of left.
4. Run the file to test your implementation. It should print Minimum value: 3 and Maximum value: 24.

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

    def add_child(self, data):
        if data == self.data:
            return  # Node already exists

        if data < self.data:



            # Add to left subtree
            if self.left:
                self.left.add_child(data)
            else:
                self.left = BinarySearchTreeNode(data)
        else:



            # Add to right subtree
            if self.right:
                self.right.add_child(data)
            else:
                self.right = BinarySearchTreeNode(data)




    # --- YOUR CODE HERE ---
    def find_min(self):



        # Implement the iterative solution to find the minimum value.
        # Start at the current node ('self') and loop down the left side.
        # Handle the case where the tree might be empty (though our test case isn't).
        pass # Replace this with your implementation

    def find_max(self):



        # Implement the iterative solution to find the maximum value.
        # The logic is the mirror image of find_min().
        pass # Replace this with your implementation



    # --- END OF YOUR CODE ---

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




# --- Main part of the script ---
if __name__ == '__main__':
    numbers = [12, 6, 18, 3, 11, 19, 5, 24]
    bst_root = build_tree(numbers)




    # Test your methods
    min_val = bst_root.find_min()
    print(f"Minimum value: {min_val}")

    max_val = bst_root.find_max()
    print(f"Maximum value: {max_val}")

    def find_min(self):
        """Finds the smallest value in the tree."""
        current = self



        # Loop down to find the leftmost leaf
        while current.left is not None:
            current = current.left
        return current.data

    def find_max(self):
        """Finds the largest value in the tree."""
        current = self



        # Loop down to find the rightmost leaf
        while current.right is not None:
            current = current.right
        return current.data

Conclusion

Congratulations on completing the module on Trees and Binary Search Trees! Today, you successfully implemented a solution to a classic algorithm problem, which is a great skill for technical interviews.

Key Takeaways:

• The minimum value in a BST is always the leftmost node, and the maximum value is the rightmost node.
• This can be found using an iterative approach with a while loop, which has an efficient space complexity of $O(1)$.
• It can also be solved recursively, which can lead to more concise code but uses $O(h)$ space for the call stack.
• Both methods have a time complexity of $O(h)$, directly linking back to our previous lesson on the importance of tree balance for performance.

Preview of the Next Lesson:

We have now covered several fundamental data structures: arrays/lists, linked lists, stacks, queues, hash tables, and trees. You're building a strong foundation. In the next module, we will begin our exploration of graphs. We'll start by defining what graphs are, the different types that exist, and how we can represent these complex networks in Python code.