Suppose that d 2 is an integer constant. In a d-ary tree, each node has at most d nonempty subtrees. For example, the trees discussed along with heaps had d = 2. We can represent a nearly complete d-ary tree with n nodes using an array whose indexes range from 0 to n1. (This is different from Cormens arrays, whose indexes range from 1 to n.) Suppose that i is the index of a node in the array. Then CHILD(i, j) is the index of the jth child of the node at i, where 1 j d. If there is no such child, then CHILD(i, j) n. Also, PARENT(i) is the index of the parent of the node at i. If there is no such parent, then PARENT(i) < 0.

1a. Show a short algorithm for CHILD. Your algorithm must run in (1) time.

1b. Show a short algorithm for PARENT. Your algorithm must run in (1) time.