This discussion is archived
1 Reply Latest reply: Oct 25, 2007 2:29 PM by 807600 RSS

Fun with trees

807600 Newbie
Currently Being Moderated
Hello all. We're doing recursion/trees in our CS class but I'm a tad bit stuck on a problem. We need to come up with some code to check if a tree is Isomorphic, which I have never heard of but apparently it means the trees are the same structure. I didn't find this to be too bad and I wrote some code for it that I think works but I haven't tested it yet.
public static boolean isIsomorphic(TreeNode s, TreeNode t) 
{ 
     if((s==null && t!=null) || (s!=null && t==null))
          return false;
     else if(s==null && t==null)
          return true;
     return isIsomorphic(s.left,t.left) && isIsomorphic(s.right,t.right); 
}
The tricky part is determining if a tree is quasi-isomorphic, which apparently means that if you swap children you get isomorphic trees. I have a little code written out but I know it isn't right as I can only really think of a base case. Anyone have any tips to get me thinking in the right direction? I'm not looking for an answer just a little bit of insight
public static boolean isQuasiIsomorphic(TreeNode s, TreeNode t)
{
     if(isIsoMorphic(s,t) || isIsoMorphic(swapTrees(s),t))
          return true;
     //Other case
     return false;
}     
public void swapTrees(TreeNode s)
{
     TreeNode hold = s.left;
     s.left = s.right;
     s.right = hold;
return s;
}
Edited by: JFactor2004 on Oct 25, 2007 4:18 PM
  • 1. Re: Fun with trees
    807600 Newbie
    Currently Being Moderated
    1. Shouldn't you methods take the data stored at each node into consideration or is the tree just a graph structure with no further information?

    2. I would define the quasi method directly, without calling on isIso. Also, I don't like your swap method -- you shouldn't mutate the tree in the course of these methods!