Tree symmetry

[techie1991]

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?

[Narue]

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.

[techie1991]

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..

[JeffGrigg]

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. :)

[techie1991]

@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]

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

You asked for test cases.

Sorry about the Java assumption; I hang out in the Java category of this site much more than Software Development; my mistake. (There are also good xUnit testing frameworks for Python and C++.)

The example code you gave shows two recursive tree traversal algorithms. But nothing regarding tree balancing. Hmmm... It leaves me confused. Should we make assumptions as to what you mean by symmetry?