SE250:lab-6:twon069

Task 1

After looping through 100 times, the height of the tree seen to increasing less and less while having large variation between a logarithmic graph.

	for (i = 0; i<100; i++){
		x = makeRandomTree(i);
		printf("size = %d height = %d\n", i, height(x));
	}

Task 2

Sounds easy, basically traverse through to find the right most or left most node to find the minimum or maximum

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

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

• However after testing the code, it seen wrong... giving me a weird number each time, I'm not sure whether it is the implementation thats wrong, or the tree is showing it wrong. The tree was REALLY and i mean REALLY hard to understand, it doesn't even look like a tree...

• After few twitching with the code, I realize I wasn't showing the correct number, and changing &y->key to y->key did the trick. (I should relearn pointers... sigh...)

Task 3

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

• This was easy as well, basiclly just a set of rules and which way to go depending on whether the key is larger or smaller at current node.

Task 4

• Pre-order, after fiddling around through my notes, it meant traversing tree this way "root->left->right"