Disconnect node p from its parent and append it to the children list of node q.

If q was in the sub-tree of node p (case 1), get the parent node of p and replace p in its children list with q.

If p was the root of the tree, make q the root of the tree.