GATE 2013 CS (CS1) – Question 17

Programming and Data Structures · Trees and Binary Search Trees · 1 mark · Multiple choice

What is the tightest worst-case upper bound for inserting into a binary search tree with n nodes?

$O(1)$
$O(\log n)$
$O(n)$
$O(n\log n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $O(n)$

Explanation

An unrestricted BST may be a chain of n nodes. Inserting a key beyond its end traverses the entire chain, taking linear time. Since at most n existing nodes are visited, the tight bound is O(n), C. A logarithmic guarantee requires balancing.

More Trees and Binary Search Trees questions

GATE 2013 CS (CS1) Q53 – A BST has preorder 30,20,10,15,25,23,39,35,42. Find its postorder.
GATE 2011 CS (CS1) Q39 – An unlabelled binary-tree shape has n nodes and n distinct keys are supplied. In how many…
GATE 2010 CS (CS1) Q20 – In a binary tree with n nodes, every node has an odd number of descendants, counting…
GATE 2015 CS (CS2) Q23 – A binary tree T has 20 leaves. How many nodes have exactly two children?
GATE 2015 CS (CS3) Q21 – A binary tree has 200 leaves. How many nodes have exactly two children?
GATE 2015 CS (CS3) Q27 – Insert 71,65,84,69,67,83 into an empty binary search tree in this order. Which element is…

All Trees and Binary Search Trees questions →