Dobrar nodos de uma árvore binaria em C

Como implementar uma funcao para dobrar a quantidade de nodos de uma arvore criando para cada nodo, um novo pai, satisfazendo

as seguintes condicoes:

 -se o nodo n tiver chave K que é par, seu pai é um novo nodo que tem chave K+1 e n será seu filho esquerdo;

 -se o nodo n tiver chave K que é impar, seu pai é um novo nodo que tem chave K-1 e n será seu filho direito;

Se alguem puder me ajudar agradeço!