I was trying to find a solution for checking the symmetry of a tree.
I would like to get some comments on the approach.. I am trying to do it by modifying the inorder traversal thing..
The pseudo code is:

``````// since the structure should be similar
string in1,in2;

func inorder (root): //normal inorder traversal
static int i;
if root==NULL: return;
if (root->left!=NULL):
in1[i++] = 'L';
inorder(root->left);
if (root->right!=NULL):
in1[i++] = 'R';
inorder(root->right);

func modified_inorder (root):

// modified inorder traversal. This one flips the traversal order from (root,left,right) to (root,right,left).

static int i;
if root==NULL: return;
if (root->right!=NULL):
in1[i++] = 'L';
inorder(root->right);
if (root->left!=NULL):
in1[i++] = 'R';
inorder(root->left);

string_compare(in1,in2); //this should provide the result by comparing the strings formed by traversals.``````

Now, would this work?

Now, would this work?

What an odd question. Why don't you write up a quick test to see if it works? If it does, then try to break it with pathological cases.

ok, I was actually asking for some test cases (maybe my selection of words wasn't good) for which this approach may fail, and luckily I got one myself..

1. If root is null, is the tree symmetrical?
2. If the root node exists, but it has no children, is it symetrical?
3. If the root node exists, and it has a left child but no right child, is it symmetrical?
4. (The rest left as an excercise for the student. :-/)

P.S. You might try using JUnit. It's good. It won't write the tests for you. You'll still have to think of them and write them. But it will run the tests, once you write them. :)

@JeffGrigg: Can you please elaborate what are you trying to say..?! I mean are you trying to explain the concept of symmetry?

and I don't code in Java (for your advice on JUnit). I prefer C,C++ (if the concepts are deep) or Python otherwise, which has good support for testing.. Anyways I never asked for any help on tools, so you might have assumed it..

@JeffGrigg: Can you please elaborate what are you trying to say..?! ...