Inverting/Mirroring a Binary Tree. Method isn't leaving the input tree intact?

Question

I'm new to Java (only been programming a month) and so I've been practicing some concepts. So if this is a naive or stupid question please be patient with me. I've only ever programmed in MATLAB before!

I just successfully inverted a binary tree (on my first try too!). However, I'm struggling with why my method is actually modifying the tree that I'm passing as input as opposed to leaving it intact and simply returning an inverted variant. In short, after the following line in my main function:

inverse = invertBinaryTree(root);

'inverse' and 'root' are both equal and they're the inverted version of 'root' BEFORE I passed 'root' into the method 'invertBinaryTree'. Please, I'm losing my mind trying to understand this behavior!

Matter of fact, I even tried creating a secondary method 'invertBinaryTree2' and this variant copies the input to a placeholder node and operates on the placeholder node instead of the input; however, this doesn't help things, my input still remains changed!

Here is my first entire main function with the supporting functions. Both invertBinaryTree and invertBinaryTree2 behave the same way, even though I'm copying root into a placeholder variable!

public class leetCode_InvertBinaryTree {

public static void main(String[] args) {
    /*
     * initializing some binaryNodes for the tree
     */
    binaryNode a = new binaryNode(4);
    binaryNode b = new binaryNode(2);
    binaryNode c = new binaryNode(7);
    binaryNode d = new binaryNode(1);
    binaryNode e = new binaryNode(3);
    binaryNode f = new binaryNode(6);
    binaryNode g = new binaryNode(9);
    binaryNode inverse;
    
    /*
     * just building the tree
     */
    a.left = b;
    a.right = c;
    b.left = d;
    b.right = e;
    c.left = f;
    c.right = g;
    
    /*
     * Here is the issue!
     */
    System.out.println("Before inverting, root's left branch contains: " + a.left.data);
    inverse = invertBinaryTree(a);
    System.out.println("After inverting, root's left branch contains: " + a.left.data);
    System.out.println("After inverting, inverse's left branch contains: " + inverse.left.data);
}

public static binaryNode invertBinaryTree(binaryNode root){
    if(root.right == null && root.left == null){
        return root;
    }
    else if(root.right == null){
        root.right = root.left;
        root.left = null;
    }
    else if (root.left == null){
        root.left = root.right;
        root.right = null;
    }
    else {
        binaryNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
    root.left = invertBinaryTree(root.left);
    root.right = invertBinaryTree(root.right);
    return root;
}

public static binaryNode invertBinaryTree2(binaryNode root){
    binaryNode placeholder = root;
    if(placeholder.right == null && placeholder.left == null){
        return placeholder;
    }
    else if(placeholder.right == null){
        placeholder.right = placeholder.left;
        placeholder.left = null;
    }
    else if (placeholder.left == null){
        placeholder.left = placeholder.right;
        placeholder.right = null;
    }
    else {
        binaryNode temp = placeholder.left;
        placeholder.left = placeholder.right;
        placeholder.right = temp;
    }
    placeholder.left = invertBinaryTree(placeholder.left);
    placeholder.right = invertBinaryTree(placeholder.right);
    return root;
}

Not that it matters, but here's the binaryNode class in case it helps you help me. I've also included the output of the main function that I have posted above.

Before inverting, root's left branch contains: 2

After inverting, root's left branch contains: 7

After inverting, inverse's left branch contains: 7

public class binaryNode {

public int data;
public binaryNode left;
public binaryNode right;

/*
 * constructor for binaryNode
 */
public binaryNode(int d){
    data = d;
}}

You should look up [references and how they are handled when passed as an argument to a method](https://docs.oracle.com/javase/tutorial/java/javaOO/arguments.html). Long story short: within the method `invertBinaryTree(...)` you are modifying the original tree, that you passed into the method. — Turing85, Jul 14 '15 at 19:55
@Turing85 Thanks for the prompt reply! How is that even possible? When I pass root to the method, doesn't the method simply 'copy' root as opposed to operating on the real root? — King Hammurabi, Jul 14 '15 at 19:58
Read the link. It is all explained there. [This question](http://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value) is related to this topic as well. If `root` were cloned, method calls were terribly slow (imagine a tree with thousands of nodes, since a tree is a recursive datastructure, you would have to clone each single node within the tree...). — Turing85, Jul 14 '15 at 20:00

score 0 · Answer 1 · answered Jul 14 '15 at 20:06

0

I'd recommend you add a lot more debug statements (for example in println) to show the state of your structure at every stage of your code. It will help illustrate to you what the code is doing.

The reason for your problem is:

In this method:

public static binaryNode invertBinaryTree(binaryNode root){

...you are passing in the node, a pointer (a reference) to an object of class binaryNode. **Incidentally, most style conventions dictate you call that something more like BinaryNode (the capitalization is standardized)...

In this line in class binaryNode:

public binaryNode left;

...you declare the node "left" as a member which can be modified by anyone. This member is of type "binaryNode," which means it refers to the address of a object of type "binaryNode."

In this code:

else if (root.left == null){
    root.left = root.right;

...you are setting the field called "left," which is the address of a binaryNode, to the thing returned by "right," which is the address of another binaryNode.

...and so on. You are setting the values of references, and are therefore changing the structure of the data structure.

answered Jul 14 '15 at 20:06

MonkeyWidget

956
1
9
19

References are not the same as pointers and there are no pointers in Java. – Turing85 Jul 14 '15 at 20:08
1

References are indeed pointers, just with reduced capabilities to avoid errors. You can't do pointer arithmetics on them, you can't cast them to anything you want, and so on. @Turing85 – Iamsomeone Jul 14 '15 at 22:08
@lamsomeone so you see... ever user is an administrator, he/she just cannot do everything.... You basically said it: there are differences. Just because references are implemented via pointers does not mean they **are** pointers. – Turing85 Jul 15 '15 at 06:22
@Turing85 : Would you like to opine on pointers/references in MATLAB? – MonkeyWidget Jul 15 '15 at 14:04
@MonkeyWidget We are talking about Java. What has MATLAB to do with this? – Turing85 Jul 15 '15 at 14:57
the context is: the question was asked by someone who has only ever programmed in MATLAB – MonkeyWidget Jul 15 '15 at 18:45

Inverting/Mirroring a Binary Tree. Method isn't leaving the input tree intact?

1 Answers1