Mirroring a Binary Tree in Java

Question

I am currently taking a data structures course in java at my highschool and I need help mirroring a tree. Below I have all my useful code and two ways to solve the mirrorImage method, which both always return null for some unknown reason. My main questions are, why don't these ways work? and how could I fix it? I think it could have something to do with the tree I am using itself because insert method doesn't work correctly.

Thanks in advance, this is my first time posting on Stack Overflow and I am looking forward to it!

note: this method is not homework I am just doing for my own good

public class TreeLab {

  public static void main(String[] args)
  {
    String s = "XCOMPUTERSCIENCE";

    TreeNode root = new TreeNode("" + s.charAt(1), null, null);

    for(int pos = 2; pos < s.length(); pos++)
        insert(root, "" + s.charAt(pos), pos, (int)(1 + Math.log(pos) / 
        Math.log(2)));

    insert(root, "B", 17, 5); 
    insert(root, "A", 18, 5); 
    insert(root, "C", 37, 6); //B's right child

    // display the tree sideways
    display(root, 0);

    System.out.println("\n\nMirror Image: ");
    display(root.mirrorImage(), 0);
  }


  public static void insert(TreeNode t, String s, int pos, int level) {

    TreeNode p = t;
    for(int k = level - 2; k > 0; k--)
        if((pos & (1 << k)) == 0) 
            p = p.getLeft();
        else                        
            p = p.getRight();

    if((pos & 1) == 0)
        p.setLeft(new TreeNode(s, null, null));
    else
        p.setRight(new TreeNode(s, null, null));
  } // end of insert


  //postcondition: display the tree sideways
  public static void display(TreeNode t, int level) {
    if(t == null)
        return;
    display(t.getRight(), level + 1); //recurse right

    for(int k = 0; k < level; k++)
        System.out.print("\t");
    System.out.println(t.getValue());

    display(t.getLeft(), level + 1); //recurse left
  }  // end of display

  public static TreeNode mirrorImage (TreeNode t) {

    //way 1
    /*
    if (t == null)
        return null;

    TreeNode right = t.getRight();
    TreeNode left = t.getLeft();

    t.setLeft(mirrorImage(right));
    t.setRight(mirrorImage(left));

    return t;
    */      

    //way 2
    /*
    if (t == null)
        return null;
    else
        return new TreeNode (t.getValue(), mirrorImage(t.getRight()), 
      mirrorImage(t.getLeft()));
    */      

    return null; //only here to help complile
  }
}//end of TreeLab

//TreeNode class

class TreeNode {

  private Object value; 
  private TreeNode left, right;

  public TreeNode(Object initValue) { 
    value = initValue; 
    left = null; 
    right = null; 
  }

  public TreeNode mirrorImage() {
    return null;
  }

  public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight) { 
    value = initValue; 
    left = initLeft; 
    right = initRight; 
  }

  public Object getValue() { 
    return value; 
  }

  public TreeNode getLeft()  { 
    return left; 
  }

  public TreeNode getRight()  { 
    return right; 
  }

  public void setValue(Object theNewValue)  { 
    value = theNewValue; 
  }

  public void setLeft(TreeNode theNewLeft)  { 
    left = theNewLeft;
  }

  public void setRight(TreeNode theNewRight) { 
    right = theNewRight;
  }
}

Answer 1

I believe I have found my mistake. I call root.mirrorImage() instead of mirrorImage(root), causing it to pass to the mirrorImage() method in the TreeNode() class that I generated by accident and always returns null. After changing this I know see both of the ways I solved the method work properly. Thanks Everyone!

Answer 2

In your mirrorImage mehod, you should create a new copy of the node you get as a parameter (now you just reassign its left and right attributes) and recursively make copies of its children:

public static TreeNode mirrorImage(TreeNode t) {
    if (t == null) {
        return null;
    }
    return new TreeNode(
        t.getValue(),
        mirrorImage(t.getLeft()),
        mirrorImage(t.getRight())
    );
}