What is the time complexity of insert, search, and delete operations in a binary tree in average and worst cases?

Time complexity of insertion, search, and deletion operations in a binary tree

The complexity of these operations depends on the height of the tree.

Average case

In a well-balanced binary tree, the height is approximately $log_2(n)$, where $n$ is the number of nodes.

Average case time complexity table:

Operation	Time complexity
Insertion	$O(log_2(n))$
Search	$O(log_2(n))$
Deletion	$O(log_2(n))$

Worst case

In the degenerate case, when the tree is a linked list (for example, all elements are sorted during insertion), the height of the tree is $n$.

Worst case time complexity table:

Operation	Time complexity
Insertion	$O(n)$
Search	$O(n)$
Deletion	$O(n)$

Example of a degenerate tree (a tree with one "edge" at each level):

// Example of a degenerate binary tree
// Each node has only one child

struct Node {
    int key;
    Node* left;
    Node* right;

    Node(int k) : key(k), left(nullptr), right(nullptr) {}
};

// Inserting elements in ascending order will create a degenerate tree
void insert(Node*& root, int key) {
    if (!root) {
        root = new Node(key);
        return;
    }
    if (key < root->key) {
        insert(root->left, key);
    } else {
        insert(root->right, key);
    }
}

int main() {
    Node* root = nullptr;
    insert(root, 1);
    insert(root, 2);
    insert(root, 3);
    // ... and so on
    // This will create a degenerate tree
    return 0;
}