CareerCup

here asked only structure not the data......
int symTree(node *a , node *b)
{
if(a == NULL && b == NULL)
{
return 1;
}
else if( a != NULL && b!= NULL)
{
return (//if data should be check then
//a->data == b->data &&
symTree(a->left,b->right) &&
symTree(a->right,b->left));
}
else
{
return 0;
}
}

Here is a function implemented in C++ that checks whether the tree is <b>structurally</b> symmetric or not.
The basic idea is to maintain two BFS queue - one for the left-subtree and one for the right-subtree both starting at the root. Add nodes in left_BFS from left to right and add nodes in right_BFS from right to left. Keep on matching the nodes popping from the queue until a mismatch is found or the queue is empty.

#include<queue>
using namespace std;
struct Node{
    int data;
    Node *left;
    Node *right;
} *root;

bool symTreeCheck(Node *root)
{
    bool flag = true;
    Node *l, *r;
    queue<Node*> bfs_left, bfs_right;
    bfs_left.push(root->left); bfs_right.push(root->right);
    while(flag&&!(bfs_left.empty()||bfs_right.empty()))
    {
        l = bfs_left.front(), r = bfs_right.front();
        if(l!=NULL&&r!=NULL){
                bfs_left.pop(); bfs_right.pop();
                bfs_left.push(l->left);
                bfs_left.push(l->right);
                bfs_right.push(r->right);
                bfs_right.push(r->left);
        }
        else if(l==NULL&&r==NULL){
            bfs_left.pop();bfs_right.pop();
        }
        else{
            flag = false;
            break;
        }
    }
    return flag;
}

My solution : ( left subtree : go throught left-right traversal,
right subtree : go through right-left traversal .... )


bool IsSym ( Node root )
{
return CheckSym ( root.left, root.right ) ;
}


bool CheckSym ( Node left, Node right )
{
if ( left == NULL && right == NULL )
return true;
else if ( left == NULL || right == NULL )
return false;

bool ret1 = CheckSym ( left.left, right.right );
bool ret2 = CheckSym ( left.right, right.left );

return ret1 && ret2 ;
}

Maintain two counters leftcount=0 and rightcount=0.
Take a fn
symmetric(tree *root,int leftcount,int rightcount)

Now traverse the tree by recursively calling the left sub part and the right sub part. increment leftcount by 1 each time the left sub part is called and similarly do for the rightcount on calling the right sub part.

If (leftcount==rightcount)
return true
else
return false.

Hope the logic is clear. Let me know if there are any hiccups in it.

Check mirror image?

This can be answered through a variant of inorder traversal. For example take the following tree
1
/ \
2 3
/ \ / \
4 5 6 7
\ / \ /
9 1 1 2

If you take the inorder traversal of the left subtree and instead of printing the node print whether the node is left child (L) or right child (R) w.r.t its parent. So for the left subtree you will have:
L R L L R

Similar for the right subtree you will have:
L R R L R

Now reverse the right subtree sequence:
R L R R L

flip the R to L and L to R:
L R L L R

Now this is equal to the left subtree's sequence and hence voila

<pre lang="" line="1" title="CodeMonkey26433" class="run-this">Here is Running Example.
It passes list of parallel nodes to function and returns if Symmetric.

/// <summary>
/// Assumption is that we are passing Left and Right node of Root in List
/// </summary>
/// <param name="nodes"></param>
/// <returns></returns>
public static bool IsTreeSymmetric(List<Tree> nodes)
{
bool isSymmetric = false;
if (nodes != null)
{
isSymmetric = true;
if (nodes.Count == 0)
{
return true;
}
else
{
List<Tree> furtherNodes = new List<Tree>();
int magicNumber = -1,startNumber = -1;
for (int i = 0; i < nodes.Count; i++)
{

if (i == 0)
{
startNumber = GetMagicNumber(nodes[i], furtherNodes);
}
else
{
magicNumber = GetMagicNumber(nodes[i], furtherNodes);
//If paraller node in Tree is not having same structure then break;
if (magicNumber != startNumber)
{
furtherNodes = null;
isSymmetric = false;
break;
}
}

}
if (isSymmetric)
isSymmetric = isSymmetric && IsTreeSymmetric(furtherNodes);
}
}
return isSymmetric;
}

/// <summary>
/// Gets :
/// 1:if no child for Current Node
/// 2:if Only Right Node
/// 3:if Only Left Node
/// 4:Both
/// </summary>
/// <param name="node"></param>
/// <param name="nodes"></param>
/// <returns></returns>
public static int GetMagicNumber(Tree node, List<Tree> nodes)
{
int magicNumber = -1;
if (node.Left != null && node.Right != null)
{
nodes.Add(node.Left);
nodes.Add(node.Right);
magicNumber = 4;
}
if (node.Left != null && node.Right == null)
{
nodes.Add(node.Left);
magicNumber = 3;
}
if (node.Left == null && node.Right != null)
{
nodes.Add(node.Right);
magicNumber = 2;
}
if (node.Left == null && node.Right == null)
magicNumber = 1;
return magicNumber;
}
</pre><pre title="CodeMonkey26433" input="yes">
//Symmetric Tree
Tree root = new Tree();
root.Left = new Tree();
root.Right = new Tree();

root.Left.Left = new Tree();
root.Left.Left = new Tree();

root.Right.Right = new Tree();
root.Right.Right = new Tree();
List<Tree> nodes = new List<Tree>();
nodes.Add(root.Left);
nodes.Add(root.Right);
bool r = IsTreeSymmetric(nodes);</pre>

BFS
level Order Traversal
check symmetry for each level LRLR(-11-11) || LNNNNR(-100001)

CS()
	i = 0
	j = k-1
	for each l from 0 to k/2-1
		if( a[i++] != a[j--])
			return false
	return true
	
res = true

SS()
	while(!nq.IsEmpty())
		swap(q, nq)
		res = res & CS(a, k)
		k = 0
		while(!q.IsEmpty())
			n = q.Remove()
			if(n->l)
				nq.Insert(n->l)
				a[k++] = -1
			else
				a[k++] = 0
			if(n->r)
				nq->Insert(n->r)
				a[k++] = 1
			else
				a[k++] = 0
	return res

mirror image

Create the mirror image and check the lChild and rChild pointers for each node.

Create the mirror image and check the lChild and rChild pointers for each node. The pointers should be the same, in the sense, the lChild pointer to a node at some level in both the trees should not be null. Same goes for the rChild

My algorithm generates a string for each subtree of the root and checks whether they are inverted (in terms of L and R). To generate the string, if the node is a left child, it will go to the left subchild first and vice versa for the right child (which ensures that a string in the right order is found for both). Here's the code:

string isMirrorImageWrapped(node *root, bool isLeftChild) {
  string left = "",right = "";
  if(isLeftChild && root->left) {
    left = "L";
    left += isMirrorImageWrapped(root->left, true);
  }
  if(root->right) {
    right = "R";
    right += isMirrorImageWrapped(root->right, false);
  }
  if(!isLeftChild && root->left) {
    left = "L";
    left += isMirrorImageWrapped(root->left, true);
  }
  return left + right;
}

bool isMirrorImage(node *root) {
  string s = isMirrorImageWrapped(root, true);
  int len = s.length();
  if(len%2) return false;
  if(len == 0) return true;
  string s1 = s.substr(0,len/2);
  for(int i = len/2; i < len; ++i) {
    if(s1[i - len/2] == 'L' ^ s[i] == 'R') return false;
  }
  return true;
}

bool symmetric(Node* leftNode, Node* rightNode)
{
  // symmetric cases
  if (leftNode == 0 && rightNode == 0) {
    return true;
  }

  // asymmetric cases
  if ( (leftNode == 0 && rightNode != 0) ||
       (leftNode != 0 && rightNode == 0) ||
       (leftNode->left == 0 && rightNode->right != 0) ||
       (leftNode->left != 0 && rightNode->right == 0) || 
       (leftNode->right == 0 && rightNode->left != 0) ||
       (leftNode->right != 0 && rightNode->left == 0) ) {
    return false;
  }

  // needs further checks
  return 
    symmetric(leftNode->left, rightNode->right) && 
    symmetricleftNode->right, rightNode->left);
}

Check if Left and Right subtrees are Mirror