We can sort a given set of n numbers by first building a binary search tree containing these numbers (using Tree-Insert repeated
ly to insert the numbers one by one) and then printing the numbers by an inorder tree walk. What are the worst-case and best-case running times for this sorting algorithm?
1 answer:
Worst case for binary search tree -O(n)
Best case for binary search tree -O(1)
<u>Explanation:</u>
The Binary search tree is the special type of binary tree. There are two child node
- Left child node
- Right child node
- In that, the right child node has a value greater than it’s the parent node. The left child node has value less than it’s the parent node.
- In the below fig. for inserting element 0, it must be inserted as the left child of 1. Therefore, for sorting we have traveled in reverse order from (3,2,1) this is the worst-case complexity O(n).
You might be interested in
Answer:
Explanation:
The following code is written in Python. It creates a for loop that iterates 10 times, asking the user for a number every time. It then checks if the number is inside the numArray. If it is not, then it adds it to the array, if it is then it skips to the next iteration. Finally, it prints the number of distinct numbers and the list of numbers.
numArray = []
for x in range(10):
num = input("Enter a number")
if int(num) not in numArray:
numArray.append(int(num))
print("Number of Distince: " + str(len(numArray)))
for num in numArray:
print(str(num), end = " ")
