Registered: 13 years ago
This was a question in assignment 04. According to the solutions, you basically traverse to the leftmost node and that will be the smallest node in the BST. I am not entirely convinced that this efficient. Here's my argument:
1. Assume you have an initially empty BST.
2. Now assume that you enter the following values in order:
x; x; ...; x[n]
and let x be the smallest element in the list of values.
Because the BST is initially empty, when x is entered, it becomes the root of the BST and x...x[n] follow the normal conditions. But if we traverse to the leftmost node now- we dont get the smallest value because the root is the smallest value. Am I missing something somewhere or is my logic sound?