1 Reply Latest reply: Oct 25, 2007 4:29 PM by 807600 RSS

    Fun with trees

    807600
      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
          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!