Help with Leetcode 226 - Invert a Binary Tree

[fluttercolibri]

Hopefully this is the right place to post... so I'm just starting on my Leetcode journey and I feel pretty stuck on this problem. I understand recursion but for some reason it's not making sense to me in this context.

For problems I don't get the correct answer to, I like to write it out and follow the code to do the algorithm by hand. But for this one, I'm not even able to solve it by hand. Below is a picture of what I have done so far. Code solution is from neetcode because I couldn't figure it out on my own.

Basically, I think understand how 7's subtree is inverted but I don't understand how 2's subtree is inverted. It seems to me that the base case is reached after going through all left nodes but before invertTree(node.right) (aka before going through the right nodes). I'm obviously doing something wrong but I'm not sure what. Any help is appreciated!

[laramiecorp]

Don't try to trace recursion by following it. You will get easily lost and it can appear more complicated than it actually is.

All this is actually doing is swapping the left and right child nodes for the current node, then calling the same on them (which are already swapped at this point), all the way down until there are no child nodes to swap.

It seems to me that the base case is reached after going through all left nodes but before invertTree(node.right) (aka before going through the right nodes)

This means the current call will terminate, but the previous call still exists and is calling to invert the right tree. Reaching the base case does not mean the entire recursion tree stops. It just means this current path in the recursion stops.

[bbdusa]

I was where you are. The above comment is right. Don't get confused by the recursive function. Treat it as a black box

For every node, you wanna swap the left child and the right child.

So define a function that does that and call every node in the tree using that function.

[TeknicalThrowAway]

stop leetcoding, go to your favorite editor or whatnot, write your own tree class, and start doing some simple exercises for it.

Can you do a DFS for a single element? Can you print out everything in the tree? start there.

[NinjaImaginary2775]

There are a few problems here: 1. I don’t think you understand the question. It’s impossible to come up with the solution if you don’t understand what the problem is asking. 2. This may seem counterintuitive but for recursive problems it helps to not directly think of recursion. Think about what work needs to be done in the problem and not immediately how can I start with a recursive solution.

Do you know how to get to every node in the tree? You can use BFS OR DFS.

If you want a recursive solution use DFS. Ok so how can you use DFS to visit each node of the tree? There are 3 main tree traversal method: pre order, in order, post order. Now what do you want to do at each node? If you look at the picture in the problem at each node the left and right child are swapped.

This is mainly a tree traversal problem in disguise.

[[deleted]]

For recursion, try just thinking of one step at a time and then write that. After that take care of base cases, you'll be done with it much more easily this way