I cannot fully credit this answer; a handful of my colleagues helped with some guesses and for breathing in my original idea. Many thanks to them!

Assumptions

• We cannot have the entire tree in memory, so it is not ideal for using recursion. Let's assume for simplicity that we can hold a maximum of two nodes in memory at most.

• We know n, the total number of levels in our tree.

• We can search for data in relation to the character or string in which it is located.

• The data on the disk is ordered by depth. That is, the first record on disk is the root, and the next two are its children, and the next four are its children, and so on.

• There are cases where the data is fully mirrored, and cases in which it is not. Empty data interleaved with non-empty data are considered "acceptable" unless otherwise noted.

• We have the freedom to use whatever data type we desire, as long as the values ​​can be compared for equivalence. Object equivalence testing may not be perfect, so let's say we're comparing primitives.

• Mirror means mirroring between root children. To use different terms, the left child with the grandmother and grandmother is mirrored to their right child, and the left child (parent) left child is mirrored with the right child's right child's child. This is shown in the graph below; the corresponding symbols represent the mirroring we want to test.

              G
        P*         P*
     C1&  C2^   C3^ C4&
  
        
  
          
          
          
        
  
      

An approach

We know how many nodes at each level we should expect when reading from disk - several multiples of 2 ^k . We can set up a double loop to iterate through the entire depth of the tree and count nodes at each level. Within this, we can simply compare the external values ​​for equivalence and short-circuit if we find an unequal value.

We can locate each external location using multiples of 2 ^k . The leftmost child of any level will always be 2 ^k and the rightmost child of any level will always be 2 ^{k + 1} -1.

Small Evidence : Level 1 - 2 and 3 external nodes; 2 ¹ = 2, 2 ^{1 + 1} -1 = 2 ² -1 = 3. The largest nodes of level 2 are 4 and 7; 2 ² = 4, 2 ^{2 + 1} -1 = 2 ³ -1 = 7. It could be extended to the n-th case.

pseudocode

int k, i;
for(k = 1; k < n; k++) { // Skip root, trivially mirrored
    for(i = 0; i < pow(2, k) / 2; i++) {
        if(node_retrieve(i + pow(2, k)) != node_retrieve(pow(2, (k+1)-i)) {
            return false;
        }
     }
 }
 return true;

      

        
        
        
      

    

Thoughts

This question is a great interview question because most likely they want to see you approach this issue. This approach can be terrible, it can be flawless, but the employer would like you to take your time, draw things on a piece of paper or chalkboard and ask them questions about how the data is stored, how it can be read, that there are search restrictions etc. etc.

This is not an aspect of coding that interviewers are interested in, but an aspect of problem solving.