Question

Looking for some help, i'm trying to understand Good and Bad BSTs a little better.

What are some examples of GOOD (i.e., nearly balanced) BST's. and then another example of BAD BST's.

For example, {1, 2, 3, 4, 5, 6, 7} = bad BST

while {4, 2, 6, 1, 3, 5, 7} = good BST.

Answer 1

For understanding good/bad BST, you need to understand the purpose of existence of BST

In BST every node van have atmost 2 child nodes and also nodes are placed such that smaller values are placed to its left and larger values to right.

On implementing a balanced binary search tree, the cost of insertion, deletion and searching is O(logN) where N is the number of nodes in the tree So the benefit really is that lookups can be done in logarithmic time which matters a lot when N is large.

For N nodes if the height of the tree is O(log N) and every operation described above can be performed in O(log N) then tree is considered to be good BST as it is accomplishing the task for which it is designed.

Disadvantages of Binary Search Trees -

The shape of the tree depends on the order of insertions, and it can be degenerated.When inserting or searching for an element, the key of each visited node has to be compared with the key of the element to be inserted/found.
Keys may be long and the run time may increase much.Trees thus formed are bad BST

Just consider the trees for the given keys for better understanding -

Bad BST -

Good BST -

Say you want to search whether 7(key) is present in the tree or not.In bad BST, you need to compare the key(7) to be searched with 1,2,3,4,5,6 and then finally 7 will be found That is you need to make 7 comparisons

Say we have N elements arranged in the same form then in worst case N comparisons are made Hence time complexity of searching is O(N) and similarly another operations like insert and delete will also require O(N) in this case Hence time complexity is same as that of linear search/insert/delete and that's why it is good BST

Now in good BST you will compare key(7) with 4,6 and 7 that is you need to make 3 comparisons

Say we have N elements arranged in the same form then in worst caseO(log N) comparisons are made Hence time complexity of searching is O(log N) and similarly another operations like insert and delete will also require O(log N) in this case Hence time complexity is reduced and that's why it is good BST

Hope i have answered your question satisfactorily.Leave doubts in comment section if any.In case the image is not clear, tell me through comments and I will post a better image in terms of both quality and writing.