Check if a tree is a mirror image?

Go To StackoverFlow.com

3

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

2012-04-04 18:59
by D J
Mirror image of an other tree - sll 2012-04-04 19:01
I would just iterate over the tree with two loops, one for the left branch and one for the right for every node. That way you aren't storing anything other than two node values and two loop counters in memory. If there is an odd number of nodes, then just skip it and move down the tree. Once you reach a point where the two loops return different values, the tree isn't symmetric - Blender 2012-04-04 19:02
@Blender: A bit more storage than that, I think (you need a stack to track which level of the tree you're at.) Still very efficient, though - Li-aung Yip 2012-04-04 19:09
Synchronous walk over the tree. Bail out on first difference - wildplasser 2012-04-04 19:09
What is the structure of the file that contains the tree - ElKamina 2012-04-04 20:33
@Li-aungYip, not necessarily, if the tree has parent references - svick 2012-04-05 07:37


4

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.

2015-06-23 06:33
by poorvankBhatia


2

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 2k. 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 2k. The leftmost child of any level will always be 2k, and the rightmost child of any level will always be 2k+1-1.

Small Proof: Outermost nodes on level 1 are 2 and 3; 21 = 2, 21+1-1 = 22-1 = 3. Outermost nodes on level 2 are 4 and 7; 22 = 4, 22+1-1 = 23-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.

2012-04-05 07:31
by Makoto
What if the tree is not perfect - svick 2012-04-05 07:41
node_retrieve(pow(2, (k+i)-i)) is this statement correct in the code?? It seems like the bracket i - D J 2012-04-05 07:56
if(node_retrieve(i + pow(2, k)) != node_retrieve(pow(2, (k+i)-i)) could you please explain this line in more detai - D J 2012-04-05 07:57
@svick: If the tree is imperfect, it should fail, which is desirable - the tree can't be mirrored if it's heavier on the left or the right - Makoto 2012-04-05 13:14
@DJ: The locations of the outer nodes are now outlaid in the answer. We use the call node_retrieve to seek on disk, so we don't have to pull everything in memory all at once - Makoto 2012-04-05 13:22
@Makoto, but imperfect tree can still be mirrored. Consider something like c(b(a,nil), b(nil, a)) - svick 2012-04-05 17:42
@svick: Yes, that's perfectly fine. So long as 2k == 2(k+1)-1 on whichever level, we can have blank data in the middle. If we're imbalanced on either the left or the right, then it will still be invalid - Makoto 2012-04-05 18:07


0

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;
}
2012-04-04 19:23
by wildplasser
recursion will take a huge memory since it can't be placed in memor - D J 2012-04-04 19:27
Why don't you say that in the original question - wildplasser 2012-04-04 19:30
@wildplasser: It was stated in the question. "Given a binary tree which is huge and can not be placed in memory..."Makoto 2012-04-04 19:31
Sorry, I must have overlooked that. My bad - wildplasser 2012-04-04 19:33
Ads