4 ms·
I had a less dramatic one where someone argued with me that the lookup time on a binary tree was O(H), the height of the tree, not O(log2n). I was so baffled by
by planet-and-halo 5y ago
I had a less dramatic one where someone argued with me that the lookup time on a binary tree was O(H), the height of the tree, not O(log2n). I was so baffled by the argument that I didn't realize until after the interview that I should have pointed out that the height of a binary tree is log2n.
- slavak 5y agoThey were technically correct. The lookup time on a binary search tree is O(H), which is equal to O(log2n) if the tree is balanced. Tree data structures invest a lot of complexity into keeping the tree balanced.
- planet-and-halo 5y agoDoesn't this only affect inserts and deletes though? I mean I get your point, but on a read you can assume that a binary tree is balanced (by definition). Or am I missing something?
- wtetzner 5y agoNo, not all binary trees are balanced binary trees.
- planet-and-halo 5y agoAh got it, thanks.