# Deleting smallest node in binary search tree

Posted by 34898425
Announcements Last Post
SoC Curricula 09/30/2017 01:08PM
Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
School of Computing Short Learning Programmes 11/24/2014 08:37AM
Unisa contact information 07/28/2011 01:28PM
 Deleting smallest node in binary search tree September 30, 2006 08:06PM IP/Host: ---.mweb.co.za Registered: 13 years ago Posts: 67 Rating: 0
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
 Re: Deleting smallest node in binary search tree October 03, 2006 08:57AM IP/Host: ---.saix.net Registered: 13 years ago Posts: 1,424 Rating: 0
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.