Binary search tree (array)

A BST’s inorder walk lists keys in sorted order. If you store those keys in a sorted array, lookup can be binary search (O(log n)) on the contiguous block—no pointers. The sample program uses a straightforward linear search instead; inserts and deletes still keep the array sorted by shifting, which is O(n) in the worst case, unlike a linked BST where local relinks cost O(h).

Read Binary search tree for the BST property and linked implementation. Read Binary tree using array for level-order heap-style indexing—that layout is not the same as this “sorted keys” view.

1) Sorted array = static view of BST keys

If you freeze a BST and list keys with an inorder traversal, you get a sorted sequence. Many interview problems treat “BST search in an array” as binary search on a sorted array (rotated arrays are a variation). Here we maintain that sorted order explicitly as keys are added or removed.

2) Search

With n keys in sorted order, you can use binary search for O(log n) lookups. The program below uses a simple linear scan instead (O(n)) so the flow is easy to follow; you can swap in binary search for the index lookup without changing the sorted-array idea.

3) Insert

Find the sorted insert position (the demo walks from the right end with a shift loop). Move elements right to open a slot, then store the key. Shifting costs O(n) in the worst case.

4) Delete

Locate the key (linear search in the demo), then shift everything after it left by one index. Combined lookup + shifts is O(n) in the worst case; binary search would improve only the find step to O(log n).

5) When this representation makes sense

• Read-heavy workloads: many searches, few updates.
• Small or bounded key sets where shifting cost is acceptable.
• Teaching the link between BST order and sorted arrays.

6) Complete C program

The demo uses global arr[], count, display, search (linear), insert / delete with shifting. Download binary-search-tree-array-demo.c and compile with gcc -std=c11 binary-search-tree-array-demo.c -o bst_array_demo.

#include <stdio.h>

#define MAX 100

int arr[MAX];
int count = 0;

// Display array
void display() {
    printf("Elements: ");
    for (int i = 0; i < count; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Search (linear search)
int search(int key) {
    for (int i = 0; i < count; i++) {
        if (arr[i] == key)
            return i;
    }
    return -1;
}

// Insert (keep sorted)
void insert(int key) {
    if (count == MAX) {
        printf("Array full\n");
        return;
    }

    // find position
    int i;
    for (i = count - 1; i >= 0 && arr[i] > key; i--) {
        arr[i + 1] = arr[i];  // shift right
    }

    arr[i + 1] = key;
    count++;
}

// Delete
void delete(int key) {
    int pos = search(key);

    if (pos == -1) {
        printf("Key not found\n");
        return;
    }

    for (int i = pos; i < count - 1; i++) {
        arr[i] = arr[i + 1];  // shift left
    }

    count--;
}

// Main
int main() {
    insert(50);
    insert(30);
    insert(70);
    insert(20);
    insert(40);
    insert(60);
    insert(80);

    display();

    printf("Search 40: %s\n", search(40) != -1 ? "Found" : "Not Found");

    delete(20);
    display();

    delete(50);
    display();

    insert(55);
    display();

    return 0;
}

7) Pointer BST vs sorted array (typical)

8) What’s next

For successor, predecessor, min/max, and operation recap, see Binary search tree operations; for pointer-based BST coding style and shape, see Binary search tree (linked list); for generic (non-BST) delete shapes, see Binary tree operations.

9) Step-by-step walkthrough (sorted-array “BST” demo)

Let’s walk through your simple sorted-array “BST” code step by step so you can clearly see how elements move during insert, delete, and search. Values match the order used in main().

📥 Initial insert sequence

We insert: 50, 30, 70, 20, 40, 60, 80. The array stays sorted after every step.

📊 Step-by-step insert dry run

🔍 Search operation — key 40

❌ Delete operation — delete 20

❌ Delete operation — delete 50

➕ Insert operation — insert 55

🧾 Final array

30  40  55  60  70  80

🧠 Key observations

• Insert requires shifting right.
• Delete requires shifting left.
• The array always remains sorted.

That is why insert/delete → O(n) (shifts in the worst case), and search → O(n) in this simple linear version (binary search would improve search to O(log n)).