SE250:lab-6:ssre005

Node* minimum( Node* node ) {
  Node* minimum_node = empty;
  while( node != empty ) {
   minimum_node = (node)->left;
  }

  return minimum_node;
   
}

Node* maximum( Node* node ) {
  Node* maximum_node = empty;
  while( node != empty ) {
   maximum_node = (node)->right;
  }

  return maximum_node;
   
}


Node* lookup( int key, Node* node ) {
  Node* lookup_node = empty;
  while( node != empty ) {
      lookup_node = node;
      if( key < (node)->key ){
	  node = (node)->left;
      }else{
	  node = (node)->right;
      }
  }
  
  if (lookup_node->key != key){
      lookup_node = empty;
  }

  return lookup_node;
}

Node* next_pre( Node* node ) {
    Node* next = empty;
    node = node->left;
    if( node == empty){
	while ((node->parent) != empty){
	    if((node != (node->parent)->right)){
		next = (node->parent)->right;
		return next;
    }
}

    return next;
}

This next_pre function took me a while to think about so hopefully it's correct. I used the example tree on the following wikipedia page: [1], and I am sure it makes sense for all cases of this tree.

On second thought, a few problems came up when my code was discussed with fellow student David. Looking at the diagram from the aforementioned wikipedia page, if the function was called on node E, the while loop "while ((node->parent) != empty){" would terminate the function before it reached the root node F since it does not have a parent. Since the only possible next node for the function to return would be G, an if statement checking for this condition was added to make the returned value G. However, if the tree was traversing upwards from the right branch, the function may return G if no next is found. Thus another condition was added to check for this. If none of these conditions are met then next defaults to empty. Hopefully this is more accurate.

Node* next_pre( Node* node ) {
    Node* next = empty;
    node = node->left;
    if( node == empty){
	while ((node->parent) != empty){
	    node = node-> parent;
	    if(((node != (node->parent)->right))&&(((node->parent)->right) != empty)){
		next = (node->parent)->right;
			    }
	    if((((node->parent)->parent) == empty)&&((node->parent)->right) != empty){
		next = (node->parent)->right;
			    }
	}

	return next;
    }
}