CSCI 340 BST Implementation Guide: Traversals, Insert, Remove & More

Understanding Binary Search Trees for CSCI 340 Assignment 7

Binary search trees (BSTs) are a fundamental data structure in computer science, and implementing one is a rite of passage. In CSCI 340 Assignment 7, you'll build a fully functional BST without auto-balancing, but your insertion and removal functions will return information that paves the way for future balancing. This guide walks through each required function, from tree traversals to BST-specific operations, with code snippets and real-world analogies to solidify your understanding.

Why BSTs Matter: A Trend Analogy

Think of a BST like the leaderboard of a popular battle royale game like Fortnite or Call of Duty. Players are ranked by score (the key). To find a player's rank quickly, you don't scan the entire list; you navigate the tree: left for lower scores, right for higher. Inserting a new player is like adding a new score to the leaderboard while maintaining order. Removing a player? You must adjust the tree so the leaderboard stays valid. This is exactly what your bst_insert and bst_remove_value functions do.

General Binary Tree Functions (bintree.h)

These functions work on any binary tree, not just BSTs. They are the foundation.

Tree Traversals: Preorder, Inorder, Postorder, Levelorder

Traversals visit every node in a specific order. They are like different ways to list items in a tournament bracket.

• Preorder (root, left, right): Visit the root first, then left subtree, then right. Useful for copying a tree.
• Inorder (left, root, right): Visits nodes in sorted order for a BST. Like reading a sorted list.
• Postorder (left, right, root): Visit children before parent. Used to delete a tree.
• Levelorder (breadth-first): Visit nodes level by level. Like scanning a tournament bracket round by round.

Implementation tip: Use recursion for the first three, and a queue for levelorder. Here's a sample inorder function:

void inorder(struct node *root, void (*fn)(struct node*)) {
    if (root == NULL) return;
    inorder(root->left, fn);
    fn(root);
    inorder(root->right, fn);
}

delete_tree, height, count

• delete_tree(root): Frees all nodes. Use postorder traversal to delete children before parent.
• height(node): Returns the height (max depth). Recursively compute 1 + max(height(left), height(right)).
• count(root): Returns total nodes. Recursively sum 1 + count(left) + count(right).

int count(struct node *root) {
    if (root == NULL) return 0;
    return 1 + count(root->left) + count(root->right);
}

Binary Search Tree Functions (bst.h)

Now the BST-specific operations. These assume the tree obeys the BST property: left child < parent < right child.

bst_find

Searches for a value. Compare with current node; if equal, return node; if less, go left; if greater, go right. Returns NULL if not found.

struct node* bst_find(struct node *root, int value) {
    if (root == NULL || root->data == value)
        return root;
    if (value < root->data)
        return bst_find(root->left, value);
    else
        return bst_find(root->right, value);
}

bst_insert

Inserts a new node while maintaining BST property. Recursively find the correct spot, then attach. Return information useful for future balancing (e.g., the depth of insertion).

int bst_insert(struct node **root, int value) {
    if (*root == NULL) {
        *root = create_node(value);
        return 0; // depth 0 for root
    }
    if (value < (*root)->data) {
        int depth = bst_insert(&(*root)->left, value);
        return depth + 1;
    } else if (value > (*root)->data) {
        int depth = bst_insert(&(*root)->right, value);
        return depth + 1;
    } else {
        // value already exists; handle as needed (e.g., do nothing)
        return -1;
    }
}

Notice the return type is int to give insertion depth. This is key for future balancing algorithms like AVL or Red-Black trees.

bst_remove_value

Removes a node with the given value. Three cases:

1. Leaf: Simply delete.
2. One child: Replace node with its child.
3. Two children: Find the inorder successor (smallest in right subtree), copy its value, then recursively delete the successor.

Return information (e.g., the depth of the removed node) to help with balancing.

int bst_remove_value(struct node **root, int value) {
    if (*root == NULL) return -1;
    if (value < (*root)->data) {
        int depth = bst_remove_value(&(*root)->left, value);
        return depth == -1 ? -1 : depth + 1;
    } else if (value > (*root)->data) {
        int depth = bst_remove_value(&(*root)->right, value);
        return depth == -1 ? -1 : depth + 1;
    } else {
        // found node to delete
        struct node *temp = *root;
        int depth = 0; // or compute actual depth if needed
        if (temp->left == NULL) {
            *root = temp->right;
            free(temp);
        } else if (temp->right == NULL) {
            *root = temp->left;
            free(temp);
        } else {
            struct node *successor = temp->right;
            while (successor->left != NULL)
                successor = successor->left;
            int successor_value = successor->data;
            bst_remove_value(&temp->right, successor_value); // remove successor
            temp->data = successor_value;
        }
        return depth;
    }
}

is_bst

Validates whether a given binary tree is a BST. Use recursion with min/max bounds.

int is_bst_helper(struct node *root, int min, int max) {
    if (root == NULL) return 1;
    if (root->data <= min || root->data >= max) return 0;
    return is_bst_helper(root->left, min, root->data) &&
           is_bst_helper(root->right, root->data, max);
}
int is_bst(struct node *root) {
    return is_bst_helper(root, INT_MIN, INT_MAX);
}

bst_minimum and bst_maximum

Find the smallest (leftmost) and largest (rightmost) values.

struct node* bst_minimum(struct node *root) {
    if (root == NULL) return NULL;
    while (root->left != NULL) root = root->left;
    return root;
}
struct node* bst_maximum(struct node *root) {
    if (root == NULL) return NULL;
    while (root->right != NULL) root = root->right;
    return root;
}

successor

Finds the inorder successor of a given node. If node has a right child, successor is the minimum of the right subtree. Otherwise, go up until you find a node that is the left child of its parent.

struct node* successor(struct node *node) {
    if (node == NULL) return NULL;
    if (node->right != NULL)
        return bst_minimum(node->right);
    struct node *parent = node->parent; // assumes parent pointer exists
    while (parent != NULL && node == parent->right) {
        node = parent;
        parent = parent->parent;
    }
    return parent;
}

Note: This function requires a parent pointer in the node structure. If not provided, you may need to search from the root.

Bringing It All Together: A Modern Twist

BSTs are everywhere. In AI, decision trees are a form of BST for classification. In finance, order books in stock exchanges use BSTs to match buy/sell orders. In gaming, a BST can store player scores for quick leaderboard queries. Even Google Maps uses tree structures for spatial indexing. As you implement these functions, think of how they power the apps you use daily.

For CSCI 340, test your BST with random insertions and removals, then verify with is_bst and traversals. Use height to check if the tree is balanced (though it won't be for sorted input). This assignment is your stepping stone to advanced trees like AVL and Red-Black.

Remember: The return values from insert and remove are crucial for future enhancements. Keep them accurate. Good luck with Assignment 7!