Root the tree at node ~1~. Now notice that if we had a function ~F~ such that ~F(n)~ colors the whole subtree of node ~n~ black (except maybe ~n~ itself) and returns us to ~n~ in the process, we can easily solve the problem. Let ~p~ be the parent of ~n~. Then after entering ~n~ do ~F(n)~. If ~n~ is black, go to ~p~ and never return to that subtree again. Otherwise, go from ~n~ to ~p~ then to ~n~ then to ~p~. Now ~n~ is black and we can continue to do the same for other children of ~p~ and so on.

Now it is easy to see that all that we need to do is to make DFS-like tour of the tree and upon returning from a node to a corresponding parent we check the color of the child node. If it is black, continue normally, otherwise visit it again and again return to the parent and then continue normally. The only exception is the root node as it has no parent. After finishing the tour and ending up in node ~1~, if it is black, we are done. If not, it is the only pink one and we can select any child ~c~ of ~1~ and do ~1 \to c \to 1 \to c~. Now all nodes are black.

It is recommended to do the implementation with a stack. Complexity is ~\mathcal O(N)~.