Home › Previous year questions › GATE 2020 CS › Question 51GATE 2020 CS – Question 51 Programming and Data Structures · Trees and Binary Search Trees · 2 marks · Multiple choice
In a balanced binary search tree with $n$ elements, what is the worst case time complexity of reporting all elements in range $[a,b]$? Assume that the number of reported elements is $k$.
$\Theta(\log n)$ $\Theta(\log n+k)$ $\Theta(k\log n)$ $\Theta(n\log k)$ Practise this question in The GATE Grind →
Show answer and explanation Correct answer: (B) $\Theta(\log n+k)$
Explanation Locating $a$ and $b$ takes $O(\log n)$, and an in-order traversal of the reported elements takes $O(k)$. Total $\Theta(\log n+k)$.
More Trees and Binary Search Trees questions GATE 2018 CS Q30 – The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of… GATE 2015 CS (CS1) Q15 – The height of a tree is the length of the longest root-to-leaf path in it. The maximum and… GATE 2015 CS (CS1) Q17 – Which of the following is/are correct inorder traversal sequence(s) of binary search… GATE 2015 CS (CS1) Q35 – What are the worst-case complexities of insertion and deletion of a key in a binary search… GATE 2017 CS (CS1) Q16 – Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T… GATE 2014 CS (CS1) Q22 – A rooted n-node binary tree is represented using pointers. The best upper bound for… All Trees and Binary Search Trees questions →