Answer: 2-3 trees

Question: Say we implement a 2-3 tree using the below structure. How can you implement TwoThreeNode::search() recursively?

class TwoThreeNode {
public:
    bool search(int k); // return true if key k is in the tree
private:
    int num_keys; // 1 if 1 key (2 subtrees), 2 if 2 keys (3 subtrees)
    int key[2]; // key[1] is undefined if num_keys == 1
    TwoThreeNode *child[3];
      // child[0] is the left child, child[2] is the right child,
      // and child[1] is the middle child if the node has 2 keys
      // (otherwise it is undefined).
};

Answer: Of course there are many possibilities. Here is mine.

bool
TwoThreeNode::search(int k) {
    if(k < key[0]) {
        if(child[0]) return child[0]->search(k);
        else return false;
    } else if(k == key[0]) {
        return true;
    } else if(num_keys == 2 && k < key[1]) {
        if(child[1]) return child[1]->search(k);
        else return false;
    } else if(num_keys == 2 && k == key[1]) {
        return true;
    } else {
        if(child[2]) return child[2]->search(k);
        else return false;
    }
}