Given a binary tree which is huge and can not be placed in memory, how do you check if the tree is a mirror image.

I got this as an interview question

• algorithm
• tree

If a tree is a mirror image of another tree, the inorder traversal of one tree would be reverse of another.

So just do inorder traversal on the first tree and a reverse inorder traversal on another and check if all the elements are the same.

I can't take full credit for this reply of course; a handful of my colleagues helped with some assumptions and for poking holes in my original idea. Much thanks to them!

Assumptions

• We can't have the entire tree in memory, so it's not ideal to use recursion. Let's assume, for simplicity's sake, that we can only hold a maximum of two nodes in memory.

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

• We can perform seeks on the data with respect to the character or line position it's in.

• The data that is on disk is ordered by depth. That is to say, the first entry on disk is the root, and the next two are its children, and the next four are its children's children, and so forth.

• There are cases in which the data is perfectly mirrored, and cases in which it isn't. Blank data interlaced with non-blank data is considered "acceptable", unless otherwise specified.

• We have freedom over using any data type we wish so long as the values can be compared for equivalence. Testing for object equivalence may not be ideal, so let's assume we're comparing primitives.

• "Mirrored" means mirrored between the root's children. To use different terminologies, the grandparent's left child is mirrored with its right child, and the left child (parent)'s left child is mirrored with the grandparent's right child's right child. This is illustrated in the graph below; the matching symbols represent the mirroring we want to check for.

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

Approach

We know how many nodes on each level we should expect when we're reading from disk - some multiple of 2^k. We can establish a double loop to iterate over the total depth of the tree, and the count of the nodes in each level. Inside of this, we can simply compare the outermost values for equivalence, and short-circuit if we find an unequal value.

We can determine the location of each outer location by 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 Proof: Outermost nodes on level 1 are 2 and 3; 2¹ = 2, 2¹⁺¹-1 = 2²-1 = 3. Outermost nodes on level 2 are 4 and 7; 2² = 4, 2²⁺¹-1 = 2³-1 = 7. One could expand this all the way to the nth 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 sort of question is a great interview question because, more than likely, they want to see how you would approach this problem. This approach may be horrible, it may be immaculate, but an employer would want you to take your time, draw things on a piece of paper or whiteboard, and ask them questions about how the data is stored, how it can be read, what limitations there are on seeks, etc etc.

It's not the coding aspect that interviewers are interested in, but the problem solving aspect.

Recursion is easy.

struct node {
        struct node *left;
        struct node *right;
        int payload;
        };

int is_not_mirror(struct node *one, struct node *two)
{
if (!one && !two) return 0;
if (!one) return 1;
if (!two) return 1;
if (compare(one->payload, two->payload)) return 1;
if (is_not_mirror(one->left, two->right)) return 1;
if (is_not_mirror(one->right, two->left)) return 1;
return 0;
}