Amazon Interview Question
Software Engineer / DevelopersIs there any such thing as unsorted BST??? I don't think so...the data given to you can be sorted or unsorted which results in a unbalanced and balanced (not necessarily...but is more balanced than the tree resulting from sorted data) tree respectively.
i.e sorted data => O(n)
unsorted data => O(log n) avg case
There is nothing like ordered in a binary tree. Either it is balanced or unbalanced.
Balanced is the one which has a depth of log(n) where n is the number of nodes. Unbalanced have a depth more than log(n). Worst case depth is n.
Worst case scenario is that a binary tree is so unbalanced it becomes a linked list in which case the search time is O(n) because the depth is n.
Binary tree is always sorted when you do an inorder traversal of that tree.
Haha, good point... a sorted, balanced tree is O(log n), otherwise O(n)
- Gayle L McDowell May 17, 2005