# Assignment 4 Question 4

Posted by stevenv
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
 Assignment 4 Question 4 July 05, 2006 11:26PM IP/Host: ---.saix.net Registered: 14 years ago Posts: 613 Rating: 0
Does anybody know what is meant by "the minimum node in a binary search tree"? Does this mean the node with the smallest info value or is it referring to a node's position within the tree?

Also, why would you need to pass in a node pointer type to this function? Surely it should be a parameter-less function which will just find the node and remove it?

Steven
 Re: Assignment 4 Question 4 July 08, 2006 11:27AM IP/Host: ---.saix.net Registered: 14 years ago Posts: 613 Rating: 0
Just realised that this method must be recursive (as required in the question) so obviously you'd have to have a node pointer type parameter! I'm going with the assumption that the minimum part means that it must be the node with the smallest info value.
 Re: Assignment 4 Question 4 July 10, 2006 08:39PM IP/Host: ---.gprs.vodacom.co.za Registered: 14 years ago Posts: 1,424 Rating: 0
This seems almost too simple, am I missing something?

Binary search trees are automatically sorted to the node with the smallest info value is the one on the far left. Are we supposed to combine the delete and search operations.

An inefficient algorithm, which I'm thinking of submitting is to traverse as far left as I can to find the value of the info of that node and then call the delete function. It's inefficient because the delete function will be traversing the same route a second time in order to do it's own search for the node.
 Re: Assignment 4 Question 4 July 11, 2006 02:47PM IP/Host: ---.saix.net Registered: 14 years ago Posts: 613 Rating: 0
I basically wrote a function to traverse the left nodes of the tree and remove the node furthest to the left. If that node is null, I removed its parent and moved the right-hand siblings up a level to where the parent was. Basically combined core functionality from search and delete methods into new routine which does these two tasks. I also initially called search and delete routines but also realised that its not very efficient because of the duplication of tree traversal.
 Re: Assignment 4 Question 4 July 11, 2006 04:05PM IP/Host: ---.gprs.vodacom.co.za Registered: 14 years ago Posts: 1,424 Rating: 0
I didn't bother - I don't need the credits
Sorry, only registered users may post in this forum.