Binary Search Trees

Binary search trees

A binary search tree (BST), also called a binary sorted tree, may be empty.

A nonempty BST has these properties:

Every value in its nonempty left subtree is smaller than the root's value.
Every value in its nonempty right subtree is greater than the root's value.
Both subtrees are themselves BSTs.

Finding a node

Search starts at the root. If the tree is empty, return NULL.

Otherwise compare the root's value with the search key:

If the key is smaller, continue only in the left subtree.
If the key is greater, continue only in the right subtree.
If the values are equal, the search succeeds.

Iterative search

bool binary_search_tree_contains(binary_search_tree_t *tree, T elem) {
    if (tree == NULL) {
        return false;
    }

    node_t *node = tree->root;
    while (node != NULL) {
        if (elem < node->data) {
            node = node->left;
        } else if (elem > node->data) {
            node = node->right;
        } else {
            return true;
        }
    }
    return false;
}

Tail recursion can be rewritten as iteration to avoid recursive-call overhead.

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

Finding the minimum and maximum

The minimum is the node reached by following left pointers until there is no left child. The maximum is reached by following right pointers until there is no right child. These nodes need not be leaves.

Recursive minimum

static node_t *binary_search_tree_min(node_t *node) {
    if (node == NULL || node->left == NULL) {
        return node;
    }
    return binary_search_tree_min(node->left);
}

Iterative maximum

static node_t *binary_search_tree_max(node_t *node) {
    if (node == NULL) {
        return NULL;
    }

    while (node->right != NULL) {
        node = node->right;
    }
    return node;
}

Inserting a node

Insertion resembles search: locate the insertion position and connect the new node there.

Insertion

static node_t *__binary_search_tree_add(node_t *node, T elem) {
    if (node == NULL) {
        return binary_search_tree_node_create(elem);
    }

    if (elem < node->data) {
        node->left = __binary_search_tree_add(node->left, elem);
    } else if (elem > node->data) {
        node->right = __binary_search_tree_add(node->right, elem);
    }
    return node;
}

binary_search_tree_t *binary_search_tree_add(binary_search_tree_t *tree, T elem) {
    if (tree == NULL) {
        return NULL;
    }

    if (binary_search_tree_contains(tree, elem)) {
        return tree;
    }
    tree->root = __binary_search_tree_add(tree->root, elem);
    tree->size++;
    return tree;
}

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

Deleting a node

For a leaf, clear its parent's pointer. With one child, connect the parent directly to that child. With two children, copy the smallest value in the right subtree into the target, then remove the original successor node. Deleting the root also requires updating root.

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

QUESTION

Root 10 has children 5 and 15. Is attaching 12 as the right child of 5 valid?

QUESTION

After copying the right-subtree minimum into a node with two children, what remains?

Starting from this BST, trace the search for 10, insert 5 and draw its pointer, then delete root 8 using the right-subtree minimum. Show pointer changes, the final tree and its inorder sequence.

Binary Search Trees