QUESTION 07

What is the binary search tree ordering rule used here?

2 marks

Answer

Every key in a node’s left subtree is smaller and every key in its right subtree is larger. This example rejects duplicate insertions.

Define the BST ADT and explain searching.

5 marks

Answer in brief

A BST combines a binary-tree shape with an ordering rule that guides search, insertion and deletion.

ADT operations

A BST interface can create an empty tree, search a key, insert a new key, remove a key and traverse or destroy the tree. The interface should define duplicate handling and how absence or allocation failure is reported.

Search algorithm

Start at root.
If the current node is NULL, report not found.
If key equals its key, report found.
If key is smaller, move left; otherwise move right.

Example

For root 50, left child 30 and right child 70, searching 40 first moves left. If 30 has right child 40, the next move reaches it. The comparisons exclude the opposite subtree because all its keys lie on the wrong side of the BST ordering rule.

Shape and duplicates

Inserting sorted keys into an ordinary unbalanced BST can make a chain. A basic BST does not automatically maintain a logarithmic height. Other duplicate policies can be valid, but must be consistent with searching, insertion and deletion.

Complexity

A search follows at most one root-to-leaf path, so it takes O(h) time. A reasonably balanced shape has h = O(log n); worst-case height is O(n). An iterative search needs O(1) auxiliary space. Inorder traversal visits all n keys in sorted order under the stated policy.

Complete C example

main.c

Download main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <stdlib.h>
struct Node { int key; struct Node *left, *right; };
struct Node *insert(struct Node *root, int key, int *ok)
{
    if (root == NULL) {
        struct Node *node = malloc(sizeof *node);
        if (node == NULL) { *ok = 0; return NULL; }
        node->key = key; node->left = node->right = NULL; return node;
    }
    if (key < root->key) { root->left = insert(root->left, key, ok); }
    else if (key > root->key) { root->right = insert(root->right, key, ok); }
    return root;
}
const struct Node *search(const struct Node *root, int key)
{
    while (root != NULL && root->key != key) { root = key < root->key ? root->left : root->right; }
    return root;
}
struct Node *remove_key(struct Node *root, int key)
{
    if (root == NULL) { return NULL; }
    if (key < root->key) { root->left = remove_key(root->left, key); }
    else if (key > root->key) { root->right = remove_key(root->right, key); }
    else {
        if (root->left == NULL) { struct Node *next = root->right; free(root); return next; }
        if (root->right == NULL) { struct Node *next = root->left; free(root); return next; }
        struct Node *successor = root->right;
        while (successor->left != NULL) { successor = successor->left; }
        root->key = successor->key;
        root->right = remove_key(root->right, successor->key);
    }
    return root;
}
void inorder(const struct Node *root)
{
    if (root != NULL) { inorder(root->left); printf("%d ", root->key); inorder(root->right); }
}
void destroy(struct Node *root)
{
    if (root != NULL) { destroy(root->left); destroy(root->right); free(root); }
}

int main(void)
{
    struct Node *root = NULL; int ok = 1;
    int keys[7] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; ++i) {
        root = insert(root, keys[i], &ok);
        if (!ok) { destroy(root); puts("Allocation failed"); return 1; }
    }
    printf("Search 40: %s\n", search(root, 40) != NULL ? "Found" : "Not found");
    root = remove_key(root, 20); root = remove_key(root, 30); root = remove_key(root, 50);
    inorder(root); putchar('\n'); destroy(root); root = NULL;
    return 0;
}

Sample input and output

The example uses values in the code.

Output

Search 40: Found
40 60 70 80

Search success and failure in the same tree

Insert 50, 30, 70, 20, 40, 60, 80 into an empty BST. Use one visit for each non-null node examined. Search for 65, which is absent.

↔ Scroll horizontally on a small screen

BST search for 65
Node visited	Comparison	Next position
50	65 > 50	Right child: 70
70	65 < 70	Left child: 60
60	65 > 60	Right child: NULL

The null link means there is no further candidate. Return “not found”; do not read a key through a null pointer. Searching for 60 follows the same first two moves and succeeds at the third node.

Why the same number of keys can give different search times

Now insert the same keys in sorted order: 20, 30, 40, 50, 60, 70, 80. In an ordinary BST, each new key becomes a right child, so searching for 80 visits all seven nodes. In the earlier tree it visits only 50, 70 and 80.

Therefore the insertion order affects the tree shape. The example BST does not balance itself. Its search follows one path: short paths give fast searches, while a chain can require O(n) visits. A traversal is different: inorder traversal must visit all n nodes even when the tree is balanced.

Common mistake: check only the immediate children

The ordering rule applies to whole subtrees. Suppose 30 is the left child of 50 and 55 is the right child of 30. Although 55 is greater than its parent 30, it is still in the left subtree of 50 and violates the BST rule. A search for 55 would move right from 50 and could miss it.

Boundary cases

Searching an empty tree reports absence immediately.
Searching for the root succeeds on the first visit.
The supplied insertion function ignores a duplicate key, so a second insertion of 50 does not add another node.