17. (a) 4%

class Node {
    public int v;
    public Node lc;
    public Node rc;
    public Node p;
}

The above is pseudo-code defining a Node class used in a binary search tree $T$. In the Node, v stores the key value, lc and rc are the pointers to the left child and right child, respectively, and p is the pointer to the parent. If $T$ contains a single node X, then X.p, X.lc, X.rc are NULL. There are 3 NULL pointers in $T$. Show that there are $n+2$ NULL pointers in $T$, where $T$ is an $n$-node binary search tree.