SE250:lab-6:dsan039

Task 1:

Inserting elements in a random order. – plot height of tree vs. no. of inserted elements. Determine relationship between height and number of elements. I completed this task in a less than elegant manner, simply stacking makeRandomTree and printf statements together instead of creating a for loop. This was simple and seemed to produce similar results to everyone else – the relationship seems to be: height ~ sqrt(no. of nodes).

Task 2:

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

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

I think these work, for min value you need to go left and for max value you need to go right. I stuffed this up a couple of times, first trying to make a new node pointer inside the functions and returning them, and then changing my while loop condition, then changing it back.

Task 3:

This task caught me for a bit, i consulted the 2007 HTTB and gained the understanding required to complete and (hopehully) understand the task. Here is my code:

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

I used this code to see whether or not it works, it seems to run:

Node *tree = makeRandomTree(640);
Node *max = maximum(tree);
Node *value = lookup(max->key, tree);
printf("%d is max\n%d is looked up", max->key, value->key);

returns:
2145324179 is max
2145324179 is looked up

Task 4/5:

These tasks confused me for a while and i did not figure them out before the end of the lab. i didn't think the code was too difficult to write, it just required understanding of pre and post ordering. I read task 6 and the code in the HTTB for inserting nodes into a tree, and it looked reasonably difficult. I understood it as best i could, but did not write any code as having the answer right infront of me kinda made it unfair.