Announcements Last Post
Announcement : Programming Students at UNISA School of Computing 06/19/2019 02:01PM
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Deleting smallest node in binary search tree
September 30, 2006 08:06PM
Hi guys

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[1]; x[2]; ...; x[n]
and let x[1] be the smallest element in the list of values.

Because the BST is initially empty, when x[1] is entered, it becomes the root of the BST and x[2]...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?

Regards
avatar Re: Deleting smallest node in binary search tree
October 03, 2006 08:57AM
Trace the adding algorithm again. If x[1] indeed is the smallest node, then all subsequent nodes will be added to its right, i.e. there will be no left hand branch.
Sorry, only registered users may post in this forum.

Click here to login