If N is not even you can always go to the left son. These nodes are exponents of 2. Consider N in base 2 and a bit i, which is not the MSB. If the bit (i + 1) is set then consider i as an addition to the sum. Otherwise, we still want to add 2ⁱ to the sum, but we also want to cancel all the bits i + 1, i + 2, .. j - 1, considering j as the smallest index that is greater than i and it is of a set bit. To do so, we notice that 2^k + 1 - 2^k = 2^k. Obviously, we now can write down the signs for the (i + 1, j — 1) substring. Every position which shares the same parity with (j - 1) will be added the sum and the others will be subtracted. Doing this, we have used the nodes (i + 1..j - 1) and we have the sum 2^i + 1, from which we subtract 2ⁱ, obtaining 2ⁱ just what we wanted in the first place. We are allowed to follow this path because it is known that N ≤ 2^K.

If N is even, find the solution for N - 1. At the end, instead of going from the node 2^MSB - 1 to the last node on the left, choose the right node instead, which is 2^MSB + 1.

For example, 9 in base 2 is 1001, so we take  - 1 + ( - 2) + 4 + 8. For 10 we will simply modify the former solution, taking  + 9 instead of  + 8.