If I have a balanced binary tree and I want to search for an item in it, will the big-oh time complexity be O(n)? Will searching for an item in a binary tree regardless of whether its balanced or not change the big - oh time complexity from O(n)? I understand that if we have a balanced BST then searching for an item is equivalent to the height of the BST so O(log n) but what about normal binary trees?
0
votes
1 Answers
1
votes
The O(log n) search time in a balanced BST is facilitated by two properties:
- Elements in the tree are arranged by comparison
- The tree is (approximately) balanced.
If you lose either of those properties, then you will no longer get O(log n) search time.
If you are searching a balanced binary tree that is not sorted (aka not a BST) for a specific value, then you will have to check every node in the tree to be guaranteed to find the value you are looking for, so it requires O(n) time.
For an unbalanced tree, it might help if you visualize the worst case of being out of balance in which every node has exactly one child except for the leaf—essentially a linked list. If you have a completely (or mostly) unbalanced BST, searching will take O(n) time, just like a linked list.
If the unsorted binary tree is unbalanced, it still has n nodes and they are still unsorted, so it still takes O(n) time.
