Each node has a child pointer and next pointer. Add first node as the child of root and the next pointer of this child points to the next child of the root and so on. Essentially form a linked list of all child nodes of every node.
Node structure will contain "level" field and "parent" field. Perform BFS on the tree. Keep track of the node that was inserted just before the current node. Once the target node is found look for level change. If the parent of the target node and the "before" node is the same after level changes, then the target node has no cousin. Else, the "before" node is the rightmost cousin.
Count the number of nodes in the left half of the BST which is O(lg n). If this count >=k then the kth smallest element is on the left side, so search the left half else search the right half.- GK May 15, 2014