GATE CS 2013 Q.7 (CS Q.7): Binary Trees, Binary Search Trees and Balanced Trees

Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of $n$ nodes?

$O(1)$

$O(\log n)$

$O(n)$

$O(n \log n)$

Official answer and solution

Official answer: C
From: Official GATE 2013 answer key

Solution

Consider the worst-case shape of a binary search tree to find the tightest upper bound on insertion time.

In a binary search tree (BST) of $n$ nodes:

To insert a new object, the algorithm compares keys starting at the root and descends down to an empty leaf position.
The time complexity of insertion is proportional to the height $h$ of the BST.
In the worst case (for example, when keys are inserted in strictly ascending or descending sorted order), the BST degenerates into a linear chain (skewed tree) of height $h = n$ .
In this worst-case configuration, insertion takes $\Theta(n)$ time.

Therefore, the tightest upper bound representing the insertion time in a general (unbalanced) BST of $n$ nodes is $O(n)$ .

Final answer

Option (C)

Common trap

Assuming the tree is balanced and stating $O(\log n)$ , which only applies to self-balancing BSTs like AVL or Red-Black trees.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2013 Computer Science and Information Technology (CS)
Question: 7 of 65, printed as CS Q.7
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source