Discussion about how to retrieve an i-th element in the j-th level of a binary tree algorithm

Question

I am solving some problems from a site called codefights and the last one solved was about a binary tree in which are:

Consider a special family of Engineers and Doctors. This family has the following rules:

Everybody has two children. The first child of an Engineer is an Engineer and the second child is a Doctor. The first child of a Doctor is a Doctor and the second child is an Engineer. All generations of Doctors and Engineers start with an Engineer.

We can represent the situation using this diagram:

            E
       /         \
      E           D
    /   \        /  \
   E     D      D    E
  / \   / \    / \   / \
 E   D D   E  D   E E   D

Given the level and position of a person in the ancestor tree above, find the profession of the person. Note: in this tree first child is considered as left child, second - as right.

As there is some space and time restrictions, the solution can not be based on actually constructing the tree until the level required and check which element is in the position asked. So far so good. My proposed solution written in python was:

def findProfession(level, pos):

    size = 2**(level-1)
    shift = False    

    while size > 2:
        if pos <= size/2:
            size /= 2
        else:
            size /= 2
            pos -= size
            shift = not shift

    if pos == 1 and shift == False:
        return 'Engineer'
    if pos == 1 and shift == True:
        return 'Doctor'
    if pos == 2 and shift == False:
        return 'Doctor'
    if pos == 2 and shift == True:
        return 'Engineer'

As it solved the problem, I got access to the solutions of other used and I was astonished by this one:

def findProfession(level, pos):
    return ['Engineer', 'Doctor'][bin(pos-1).count("1")%2]

Even more, I did not understand the logic behind it and so we arrived to this question. Someone could explain to me this algorithm?

Answer 1

This type of sequence is known as the Thue-Morse sequence. Using the same tree, here is a demonstration of why it gives the correct answer:

p is the 0-indexed position

b is the binary representation of p

c is the number of 1's in b

                  p0
                   E
                  b0
                  c0
            /            \
         p0                p1
         E                  D
        b0                 b1
        c0                 c1
    /        \         /        \
   p0        p1       p2        p3
   E          D        D         E
   b0        b1       b10       b11
   c0        c1       c1         c2
  /  \      /  \     /  \       /  \
p0   p1   p2   p3   p4   p5   p6   p7
 E    D    D    E    D    E    E    D
b0   b1   b10  b11  b100 b101 b110 b111
c0   c1   c1   c2    c1   c2   c2   c3

c is always even for Engineer and odd for Doctor. Therefore:

index = bin(pos-1).count('1') % 2
return ['Engineer', 'Doctor'][index]

Answer 2

Let's number the nodes of the tree in the following way:

1) the root has number 1

2) the first child of node x has number 2*x

3) the second child of node x has number 2*x+1

Now, notice that each time you go to the first child, the profession stays the same, and you add a 0 to the binary representation of the node. And each time you go to the second child, the profession flips and you add a 1 to the binary representation.

Example: Let's find the profession of the 4th node in the 4th level (last level in the diagram you have in the question). First we start at the root with number 1, then we go to the first child with number 2 (10 binary). After that we go to the second child of 2 which is 5 (101 binary). Finally, we go to the second child of 5 which is 11 (1011 binary).

Notice that we started with only one bit equal to 1, then every 1 bit we added to the binary representation flipped the profession. So the number of times we flip a profession is equal to the (number of bits equal to 1) - 1. The parity of this amount decides the profession.

This leads us to the following solution:

X = number of bits equal to 1 in [ 2^(level-1) + pos - 1 ]

Y = (X-1) mod 2

if Y is 0 then the answer is "Engineer" Otherwise the answer is "Doctor"

since 2^(level-1) is a power of 2, it has exactly one bit equal to 1, therefore you can write:

X = number of bits equal to 1 in [ pos-1 ]

Y = X mod 2

Which is equal to the solution you mentioned in the question.