Each insertion costs $O(\log(\text{size}))$, and the size stays between $n$ and $n^2+n$, so each insertion is $\Theta(\log n)$. Total is $\Theta(n^2\log n)$.
More Trees and Binary Search Trees questions
GATE 2020 CS Q51– In a balanced binary search tree with n elements, what is the worst case time complexity…
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…