EXISTS

• Inputs: T and D.
• Outputs: true or false.
• Postconditions: true if there exists a tree in direction D.

void in_order_traverse
       (binary_tree *t, void (*f) (element))
{
  if (! is_empty(t)) {
    if (exists(t,Left))
      in_order_traverse(get_tree(t,Left),f);
    f(get_rootvalue(t));
    if (exists(t,Right))
      in_order_traverse(get_tree(t,Right),f);
  }
}

WHICH_SIDE

• Input: T.
• Output: a direction (Left or Right).
• Preconditions: T is a subtree
• Postconditions: returns Left if T is a left subtree, Right if it is a right subtree.