Guided Project: Binary Trees II

Project Overview

Learning Goals

Understand BST search principles
Implement recursive search logic
Optimize search operations
Handle edge cases properly

Prerequisites

Binary Search Tree basics
Recursive function concepts
JavaScript fundamentals
Basic tree traversal

Key Concepts

BST Properties

A Binary Search Tree has these key properties:

Left subtree contains only nodes with values less than the node's value
Right subtree contains only nodes with values greater than the node's value
Both left and right subtrees are also BSTs
No duplicate values (in this implementation)

Search Operation

Search operation advantages:

O(log n) time complexity for balanced trees
Efficient for large datasets
Simple recursive implementation
No need to visit all nodes

BST Recursive Search Implementation

Step-by-Step Implementation

Step 1: Node Class

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

Step 2: Search Method

                                    def search(self, value):
    return self._search_recursive(self.root, value)
                                

Step 3: Base Cases

                                    def _search_recursive(self, node, value):
    # Base case 1: Empty tree or not found
    if node is None:
        return None

    # Base case 2: Value found
    if node.value == value:
        return node

    # Recursive cases
                                

Step 4: Recursive Cases

                                    # Inside _search_recursive after base cases
if value < node.value:
    # Search left subtree (smaller values)
    return self._search_recursive(node.left, value)
else:
    # Search right subtree (larger values)
    return self._search_recursive(node.right, value)
                                

Step 5: Complete Implementation

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

    def search(self, value):
        return self._search_recursive(self.root, value)

    def _search_recursive(self, node, value):
        # Base case 1: Empty tree or not found
        if node is None:
            return None

        # Base case 2: Value found
        if node.value == value:
            return node

        # Recursive cases
        if value < node.value:
            # Search left subtree (smaller values)
            return self._search_recursive(node.left, value)
        else:
            # Search right subtree (larger values)
            return self._search_recursive(node.right, value)
                            

Practice Challenge

Now that you've learned how to implement a recursive search in a Binary Search Tree, try these challenges to reinforce your understanding.

Challenge 1: Implement findMin and findMax

Implement two methods to find the minimum and maximum values in a BST.

Requirements:

Implement findMin() to find the minimum value in the BST
Implement findMax() to find the maximum value in the BST
Both should return the node with the min/max value (not just the value itself)
Both should be implemented recursively

Starter Code:

                            class BST:
    # ... existing implementation

    def find_min(self):
        # Your code here
        pass

    def _find_min_recursive(self, node):
        # Your code here
        pass

    def find_max(self):
        # Your code here
        pass

    def _find_max_recursive(self, node):
        # Your code here
        pass
                        

Challenge 2: Count Nodes in Range

Implement a method that counts how many nodes have values in a given range [min, max].

Requirements:

Implement countNodesInRange(min, max) that returns the count of nodes with values between min and max (inclusive)
Use recursive approach to efficiently traverse only necessary parts of the tree
Handle edge cases properly

Starter Code:

                            class BST:
    # ... existing implementation

    def count_nodes_in_range(self, min_value, max_value):
        return self._count_nodes_in_range_recursive(self.root, min_value, max_value)

    def _count_nodes_in_range_recursive(self, node, min_value, max_value):
        # Your code here
        pass
                        

Challenge Practice Resources:

If you want more practice with BST operations, check out these LeetCode problems:

Guided Project: BST Recursive Search

Project Overview

Learning Goals

Prerequisites

Key Concepts

BST Properties

Search Operation

BST Recursive Search Implementation

Step-by-Step Implementation

Step 1: Node Class

Step 2: Search Method

Step 3: Base Cases

Step 4: Recursive Cases

Step 5: Complete Implementation

Practice Challenge

Challenge 1: Implement findMin and findMax

Requirements:

Starter Code:

Challenge 2: Count Nodes in Range

Requirements:

Starter Code:

Challenge Practice Resources: