Erik's answers to the 331 Review questions

48.

Give some pseudo-code for the recursive algorithms that perform the following traversals:
Refer back to page 2 for the order to visit the nodes.
pre-orderin-orderpost-order
Node::PreOrder() {
  cout << key << endl;
  if( left ) left->PreOrder();
  if( right ) right->PreOrder();
}
 
Node::InOrder() {
  if( left ) left->InOrder();
  cout << key << endl;
  if( right ) right->InOrder();
}
 
Node::PostOrder() {
  if( left ) left->PostOrder();
  if( right ) right->PostOrder();
  cout << key << endl;
}

49.

You perform a pre-order traversal on a ginary tree and it prints A H C P K T. What's at the root of the tree? If there's a left child, what is it?
The first element printed out was 'A'. In the pre-order traversal, the first thing that's done is printing out the root node's value. So the root is 'A'. The next element to be printed will either be a left or right child of the root. Since 'H' is > 'A', it is a right child. So 'A' has no left child.

50.

You perform an in-order traversal of a binary tree with root 'R'. The values printed out are D K L C R T S. What values are in the left and right subtrees of R?
With the in-order traversal, any items to the left of the root are printed, then the root is printed, the the right subtree is printed. So R's left subtree is D K L C and the right subtree is T S.

51.

You perform a post-order traversal of a tree and it prints out A H C P K T. What was at the root of the tree?
In the post order, the entire left subtree is printed, followed by the right subtree, then the root. So T is at the root of the tree.

52.

J H D E Q W P X was printed form a post-order traversal. Fill out the tree based on its structure
From the post-order traversal, we know that the last element, X, is the root of the tree.
The first item to be printed out goes on the far left edge of the tree, since the post-order first tries to go to that node first. The next item printed is H. Comming up one more level, and we try the right subtree. Again, for the right subtree, we first travel to the left as far as possible. After recursing back up from the left, we go to the right. Following a return from right recursion, we print the values at their respective nodes.

53.

What are E's ancestors?
What are P's children?
 E's ancestors are P and X.
P's childtren are E D W and Q

54.

What's the maximum height of a tree with n nodes?
If the items were inserted in order (or reverse-order) the tree degenerates to a linked list of lenght (or in this case height) n.

55.

What's the minimum height of a tree with n nodes?
The height will be lg (n+1). A tree with 7 items has a minimum height of lg 8 = 3.

56.

What is a (binary max) heap? What are its properties?
A binary max heap is like a binary tree, with a few exceptions. The element at the root is always the maximum. The tree is also always as balanced as possible. It always has a near-minumum height.

57.

Can a heap contain duplicate keys? What about a binary search tree?
A heap can contain duplicates, a binary serach tree can't.

58.

What is the big O running time for finding the 3rd largest element of a binary max heap?
O(lg n). Remove two elements from the heap, then the top element will contain the 3rd largest.

59.

What is the big O running time for finding the smallest element of a binary max heap?
O(n lg n). All elements needs to be removed to get to the smallest one.
previous | next