CareerCup

from the root node, do the broad first seach for the two sub nodes. At each step, put the node into a queue. if a node is NULL, put NULL into the queue also.
After that,we got two queques. Compare these two queues side by side. Return false when the two compared node are not equal. Return true at the end

Time: O(2*N) Space: O(2*N)

we can mirror a binary tree and then check the inorder before and after the mirroring....... if it is same then it is a symmetric binary tree else not

and your definition of symmetry?

This func takes left & right child of a tree, which is going under symmetry consideration.

bool isSymmetricTree(node * ptr1, node * ptr2)
{

    if(ptr1->value != ptr2->value)
        return 0;

    return ( ( ( ptr1->left != 0 && ptr2->left != 0 ) ? isSymmetricTree(ptr1->left, ptr2->left) : (ptr1->left == ptr2->left) )
             && ( ( ptr1->right != 0 && ptr2->right != 0 ) ? isSymmetricTree(ptr1->right, ptr2->right) : (ptr1->right == ptr2->right) ) );
}

How about creating in-order, postorder or preorder traversal output of left and right sub tree of root node and comparing all the elements one by one.

any thoughts???

private void mirror(Node node) {
if (node != null) {
// do the sub-trees
mirror(node.left);
mirror(node.right);
// swap the left/right pointers
Node temp = node.left;
node.left = node.right;
node.right = temp;
}
}

//lets use preorder traversal technique 4 dis
p=root->l;
q=root->r;

for(;p!=NULL&&q!=NULL;)
{ if(p->r!=NULL&&q->l!=NULL)
{ push(s1,p->r); push(s2,q->l);
}
if(p->l!=NULL&&q->r!=NULL)
{ p=p->l;
q=q->r;
}

else
{p=pop(s1);
q=pop(s2);
}
}

if(p==q)
return "SYMMETRIC";
return "NOT SYMMETRIC"

We can also go for a diferent strategy.First we go for the in-order traversal of the Left subtree and push every node->data into a stack. Then we make and in-order traversal of the Right subtree and compare the data with the popped value of stack.If they don't match then the right subtree is not a mirror image of the left subtree and so tree isn't symmetric

We can also go for a diferent strategy.First we go for the in-order traversal of the Left subtree and push every node->data into a stack. Then we make and in-order traversal of the Right subtree and compare the data with the popped value of stack.If they don't match then the right subtree is not a mirror image of the left subtree and so tree isn't symmetric

traverse the tree by inorder traversal and reverse inorder traversal and compare the sequence.

bool isSymmetric(Node *ptr1, Node *ptr2)
{
if (!ptr1 && !ptr2)
return true;
if (!ptr1 || !ptr2)
return false;
return((ptr1->data == ptr2->data) && isSymmetric(ptr1->left, ptr2->right) && isSymmetric(ptr1->right, ptr2->left));
}

// pass root->left and root->right in this function
bool Symmetric_tree(node *ptr1,node *pt2)
{
if(!ptr1 && !ptr2)
return(true);
if(!ptr1)
return(false);
if(!ptr2)
return(false);
return((ptr1->data == ptr2->data)&&Symmetric_tree(ptr1->left,ptr2->right)&&Symmetric_tree(ptr1->right,ptr2->left))
}

From main call the function isSymmetric1 with the root node as argument

bool isSymmetric1 (Node *root)
{
    if (root == NULL)
        return true;
    for (int i = 0, int j = root->no_of_children - 1; i < j; i++, j--)
    {
        if (!isSymmetric2 (a->children[i], a[children[j])
            return false;
    }
    return (i == j)? isSymmetric (a->children[i]): true;
}

bool isSymmetric2 (Node *p, Node *q)
{
    if (p == NULL && q == NULL)
        return true;
    if ((p != NULL && q != NULL) && (p->info == q->info) && (p->no_of_children  ==                q->no_of_children)
    {
        for(int i = 0, int j = no_of_children - 1; j >= 0; i++, j--)
        {
            if (!isSymmtrical2 (p->children[i], q->children[j])
                return false;
        }
        return true;
    }
    return false;
}