My answer is constant time O(1) since an implementation would naturally have the pointer to the root. However, the solution guide I am looking at argues it is O(logN).
1
-
$\begingroup$ You need to get rid of the complete tree, not just axe the root. $\endgroup$– vonbrandAug 19, 2019 at 20:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
I hope I'm not misunderstanding you, but keep in mind that you don't just have to find the node you want to get rid of. You also have to replace it with another node to still have an intact tree afterward.
For it to then still be a binary tree that node needs to be closest to the root in value. The worst case will turn out to be that all nodes have two children, and in that case the node closest in value to the root is either the leftmost leaf on the right side or the rightmost leaf on the left side.
So with deletion we're looking at two operations to perform:
- finding the element to delete (that's $\mathcal{O}(1)$ when we're deleting the root, as You've correctly pointed out)
- finding a replacement for the root (turns out to be $\mathcal{O}(\log n)$ as we'll see...)
To find that replacement you have to traverse a full path from root to leaf, which in a binary tree could be anywhere between length $\log n$ and $n$. But note that if the path were any longer than $\log n$ nodes, we'd have to have some node with only one child, in which case we can simply move that node up a level and save ourselves any further effort. (This also kind of shows that the worst case is in fact what I've claimed above since in any other case we could stop earlier.)
Thus at worst we'll have $\mathcal{O}(\log n)$.
