distance from root search of tree fails
<p>The tree is as follows:</p>

<pre class="lang-py prettyprint-override"><code>       (1,1)
       /   \
    (2,1)  (1,2)
    / \      / \
 (3,1)(2,3) (3,2)(1,3) 
      and onward
</code></pre>

<p>The root is (1,1), all values in the tree are tuples.</p>

<pre><code>Where (x,y) is an element of the tree:
The leftChild will be (x+y,y)
The rightChild will be (x,x+y)
</code></pre>

<p>I am building a function that finds the distance from the root (1,1). I cannot build the tree from scratch as it will be too time consuming.</p>

<p>I have found that 1 distance from the tuple being searched for we must subtract the the max with the min. We can work backward.</p>

<pre><code>     1      2
(3,2)-&gt;(1,2)-&gt;(1,1)
(3,2)-&gt;(3-2,2) = (1,2)-&gt;(1,2-1) = (1,1)
given this is always true:
if x &gt; y:
   newtuple = (x-y,y)
   distance += 1
else if y &gt; x:
   newtuple = (x,y-x)
   distance += 1
</code></pre>

<p>Yet because possible test cases can go up to even x = 10^50, this is even too slow.</p>

<p>So I have found a formally to find the amount of subtractions of x with y or vice versa to make a x > y change to y &lt; x and vice versa until (x,y) = (1,1).</p>

<p>So X - Y(a certain amount of times, say z) will make x less than y...
X - Y*z = y
find z via algebra... z = (Y-X)/(-Y)</p>

<p>This is my code so far:</p>

<pre><code>from decimal import Decimal
import math

def answer(M,F):
    M = int(M)
    F = int(F)
    i = 0
    while True:
        if M == 1 and F == 1:
            return str(i)
        if M &gt; F:
            x = math.ceil((F-M)/(-F))
            M -= F*x
        elif F &gt; M:
            x = math.ceil((M-F)/(-M))
            F -= M*x
        else:
            if F == M and F != 1:
                return "impossible"
        i += x
        if M &lt; 1 or F &lt; 1:
            return "impossible"

    return str(i)
</code></pre>

<p>And it's not passing some unknown test cases, yet passes all the test cases I can think of. What test cases could I be failing? Where is my code wrong?</p>

<p>p.s. used Decimal module, just removed from code to make more readible.</p>

<p>Floor division allows for no loss, but maybe -1 in error which I consider for the code below.</p>

<pre class="lang-py prettyprint-override"><code>def answer(M,F):
    M = int(M)
    F = int(F)
    i = 0
    while True:
        if M == 1 and F == 1:
            return str(i)
        if M &gt; F:
            x = F-M
            x = x//(-F)
            if F &lt; M-(F*x):
                x += 1
            M -= F*x
        elif F &gt; M:
            x = M-F
            x = x//(-M)
            if M &lt; F-(M*x):
                x += 1
            F -= M*x
        else:
            if F == M and F != 1:
                return "impossible"
        i += x
        if M &lt; 1 or F &lt; 1:
            return "impossible"

    return str(i)
</code></pre>

python algorithm data-structures tree binary-tree