<!-- language-all: lang-java -->

#Java, <s>209</s> 207 bytes

I surprised I was able to get it this short. There is probably still room for improvement. As usual, suggestions will be appreciated :)

This returns a `char[]`. Call using `a(n)`.

    char[]a;int b,c=0,d=0,e=2;char[]a(int f){java.util.Arrays.fill(a=new char[b=1<<f],'.');for(a[0]=88;d+1<e;c=(d+e)/2,a[(c%b+b)%b]=88)e=b(d=b(b(c)));return a;}int b(int f){for(;;)if(a[(++f%b+b)%b]>87)return f;}

Indented:

    char[] a;
    int b, c = 0, d = 0, e = 2;

    char[] a(int f){
        java.util.Arrays.fill(
                a = new char[
                        b = 1 << f
                        ]
                , '.'
        );
        for(
                a[0] = 88;
                d + 1 < e;
                    c = (d + e) / 2,
                    a[(c % b + b) % b] = 88
            )
            e = b(
                    d = b(
                            b(c)
                    )
            );
        return a;
    }

    int b(int f){
        for (;;)
            if (a[(++f % b + b) % b] > 87)
                return f;
    }