BST Insert Operation in DSA C++ - Time & Space Complexity

Time Complexity: BST Insert Operation

O(h)

Understanding Time Complexity

We want to understand how the time to insert a value into a Binary Search Tree (BST) changes as the tree grows.

How does the number of steps needed to insert a new value grow when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Node {
    int val;
    Node* left;
    Node* right;
};

Node* insert(Node* root, int key) {
    if (!root) return new Node{key, nullptr, nullptr};
    if (key < root->val) root->left = insert(root->left, key);
    else root->right = insert(root->right, key);
    return root;
}
    

This code inserts a new value into a BST by moving down the tree until it finds the right spot.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls moving down one level of the tree.
• How many times: Once per tree level until the correct leaf position is found.

How Execution Grows With Input

Each insert moves down the tree one step at a time, so the number of steps depends on the tree's height.

Input Size (n)	Approx. Operations (steps down tree)
10	About 3 to 10 steps
100	About 7 to 100 steps
1000	About 10 to 1000 steps

Pattern observation: If the tree is balanced, steps grow slowly (around log n). If unbalanced, steps can grow as fast as n.

Final Time Complexity

Time Complexity: O(h) where h is the tree height

This means the time depends on how tall the tree is, which can be small if balanced or large if skewed.

Common Mistake

[X] Wrong: "Insertion always takes the same time regardless of tree shape."

[OK] Correct: The tree's shape affects how far we must go down. A tall, unbalanced tree means more steps.

Interview Connect

Knowing how tree shape affects insert time helps you explain trade-offs and choose the right tree type in real problems.

Self-Check

"What if we used a self-balancing BST like an AVL tree? How would the time complexity change?"