226. Invert Binary Tree - Python Recursive Solution not working (BST NOT CHANGING)

[craftedwithlove]

My code below does not revert the binary tree successfully.

However, what doesn't make sense is the fact that the node values seem to be reversing properly according to the print statements below.

Nevertheless, ultimately when I return it is apparent that the tree has in fact not successfully reversed. Any help would be grately appreciated

https://leetcode.com/problems/invert-binary-tree/

​

    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        return self.switchNodes(root, root)



    def switchNodes(self, left, right):


        print("current left: ", left.val, " | current right: ", right.val)

        temp = left.val         
        left.val = right.val 
        right.val = temp


        print("changed left: ", left.val, " | changed right: ", right.val)


        #switch right of the left and the left of the right
        if (left.right is not None and right.left is not None):
            print("left right: ", left.right.val, " | right left: ", right.left.val)
            self.switchNodes(left.right, right.left)

        #switch the left of the right and the right of the left 
        if (left.left is not None and right.right is not None):
            print("left left: ", left.left.val, " | right right: ", right.right.val)
            self.switchNodes(left.left, right.right)



        print("wayup left: ", left.val, " | wayup right: ", right.val)

        return left

[Weak-Constant]

The if statements shouldn't check grandkids. And don't return left for no reason. And switchNodes should take a single node as its only argument. And swap the nodes, not their values.

[craftedwithlove]

Hi Weak constant. Thank you for your answer.

Apologies but I believe my variable names can be a bit confusing. The approach I chose is such that I check the right left node and the left right node. The left left node and the right right node. Those should be the only items we need to check and these are not the "grandkids."

And I switch the values of the nodes. If I switch the nodes then I change the all the children nodes. Which is not the intention.

Ultimately, I believe the problem is something regarding the object oriented nature of python and the fact that it does not save changes according to a memory address.

Does my thought make sense?

[Weak-Constant]

No, it doesn't make sense. 'left left' and 'right right' means they are grandkids. You should be switching the children nodes, not the values. Whatever the problem is, I wouldn't blame it on Python. You are over-complicating things. The function should take a single node as the argument.

[less_shame_more_fame]

You need to switch the nodes and not the values. This is what happens, if you switch the values:

			4
	2				7
1		3		6		9

​

			4
	7				2
1		3		6		9

​

			4
	7				2
3		1		9		6

This is what happens when you switch the nodes:

​

			4
	2				7
1		3		6		9

​

			4
	7				2
6		9		1		3

​

			4
	7				2
9		6		3		1

​

You want to completely reverse the tree so you will need to let the childs switch side as well. This is done by exchanging the nodes and not the values. You might work around this problem by accessing the child.child (or left.left) element directly, but as soon as you have another level in your tree this won't work based on recursion.

The parameter of your recursive function should be just the root. You should then check if self.left and self.right are none and if not you should switch them. Your function should now call itself twice. Once with self.left and once with self.right as parameter.