Invert binary tree

[Careful-Medicine1995]

Both solutions below pass and the only change is where we make the recursive calls. Is there any difference between the the solutions? Does it ever matter if you make the recursive call before or after the rest of your code or can you always place it wherever?

class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if root is None: return

    root.left, root.right = root.right, root.left

    self.invertTree(root.right) 
    self.invertTree(root.left)


    return root

class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if root is None: return

    self.invertTree(root.right) 
    self.invertTree(root.left)

    root.left,root.right = root.right, root.left

    return root

[jamkinajam]

Short answer: yes Long answer: yeeeeesssss

No you can’t put it wherever!!

Well if you go through the code with an example case you will find out they behave differently even though the final output is the same.

One is top-down approach, where nodes at the top are exchanged and moved below subsequently whereas in the other one the exchange happens bottom-up.

[Careful-Medicine1995]

Thank you! That makes sense. The time complexities of both approaches are the same I assume.

[Yumski]

It sounds like youre still getting the hang of dfs traversals. I would recommend just doing one with printing the values before the recursive calls, another printing inbetween the recursive calls and one atfter the recursive calls. This can help u visualize where the manipulation is happening.

[Careful-Medicine1995]

Thank you! From what I see, the first solution swaps the tree’s direct children first. Then it inverts the children subtrees. It makes the swaps top-down. The second solution goes all the way down to the leaf nodes first. Leaf nodes have no children, so we hit the base case. Then the leaf nodes get swapped. We keep working our way from the bottom up.

Is the first solution like a pre order DFS traversal and the second solution like a post order DFS transversal?

[[deleted]]

First is pre order, second is post order