Page 247 - DCAP407_DATA_STRUCTURE

Data Structure

delete(X, node){
if(node = NULL) //nothing to do
return
if(X<node:data)

delete(X, node:leftChild)
else if(X>node:data)
delete(X, node:rightChild)
else { // found the node to be deleted. Take action based on number of node children
if(node:leftChild = NULL and node:rightChild = NULL){
delete node
node = NULL
return

}
else if(node:leftChild = NULL){
tempNode = node
node = node:rightChild
delete tempNode}
else if(node:rightChild = NULL){

tempNode = node
node = node:leftChild
delete tempNode
}
else { //replace node:data with minimum data from right sub-tree
tempNode = findMin(node.rightChild)
node:data = tempNode:data

delete(node:data,node:rightChild)
}
}
Pseudocode for Finding Minimum Value from a Binary Search Tree
//Purpose: return least data object X in the Tree

//Inputs: binary-search-tree node node
// Output: bst-node n containing least data object X, if it exists; NULL otherwise
findMin(node)
{
if(node = NULL) //empty tree
return NULL
if(node:leftChild = NULL)
return node

240 LOVELY PROFESSIONAL UNIVERSITY