GATE CS 2013 Q7 — Binary Search Trees

To find the tightest upper bound for inserting an object into a Binary Search Tree (BST) of $n$ nodes, we must consider the worst-case scenario.

In a Binary Search Tree, the insertion operation involves traversing from the root down to a leaf position where the new node can be placed. The time complexity of this operation is proportional to the height of the tree, $h$:

Depending on the structure of the BST, the height $h$ varies:

• Best/Average Case (Balanced Tree): The height of the tree is $h = \Theta(\log n)$, leading to an insertion time of $O(\log n)$.
• Worst Case (Skewed Tree): If the elements are inserted in sorted order (e.g., $1, 2, 3, \dots, n$), the tree degenerates into a linear chain (a skewed tree). In this case, the height of the tree is $h = \Theta(n)$.

Since the question asks for the upper bound (which must cover the worst-case scenario) for a standard, un-balanced BST, the tightest upper bound is $O(n)$.