Invert Binary Tree | Leetcode  

I was watching comedy show and boom!! advertisement came: "do you know what’s the scariest thing is, not knowing how to invert a binary tree in a coding interview" and I ended up being here😂 thank you Algo expert ad😂😂😂

It was overhyped.. i was too afraid. But it looks easy after you explained it . Thanks

Telling TIme Complexities in every video would be cherry on the cake. Your videos are really good. Especially the video you talk about how to crack any interview exam. 😍😍 There is swap also in STL so this can be like this also. TreeNode* invertTree(TreeNode* tree) { if(!tree)return tree; invertTree(tree->left); invertTree(tree->right); swap(tree->left,tree->right); return tree; }

Can you make a complete series on Trees, LinkedList , OS and DBMS

why was postorder traversal used? why not others?

I'm downvoting this video simply because the writing is illegible.

The way you explain is amazing..you made the problem cakewalk.a big thanks to you.😅

time complexity = O(n) as traversal is used Space complexity - O(n) internal stack space

can we add one more condition like root->left == NULL && root->right == NULL return . Because again swapping NULL with NULL doesnt makes sense. Am I thinking correct???

Thanks. You put in a lot of effort.

Great video. Definitely made it super easy to understand compared to those big youtubers. Thanks!

adding another check may help avoid the unnecessary null swapping at the root level. :)

When you accent is this thick, you really need to include subtitles in your video. Just speak in your native language because people struggle to understand you and it's very demoralizing to novice coders.

Wow,june challenge is also here

Thanks for this... Do any swaps happen at 1:35? I mean that does our program actually get to swap the None values on the root node of 1?

Can you recommend me any book DS and Algorithms ? I am a beginner

Earlier thought the toughest, but now it seems the easiest. Thank you RU-vidr.

Thanks!..I want to clarify one thing that will this code also swap the null values of the leaf node(when leaf node becomes the root or curr)?

How is this a recursive problem ? They're the exact SAME graph! sure, you could do ... *Method 1* void Node::Reverse() { // Swap left and right pointers... Node* ptrTemp = ptrLeft; ptrLeft = ptrRight; ptrRight = ptrTemp; // And have all children do same, recursively! (ptrLeft)->Reverse(); (ptrRight)->Reverse(); } ... and then simply call head.Reverse(); But you'd need to hide it behind a Tree class, or risk a caller accidentally calling Reverse on a non-head node and possibly corrupting the tree. But what's wrong with... *Method 2* // In type 'Node' private: Node* ptrChild[2]; // child nodes are [0] and [1] ... and reverse by simply inverting the index ... i = 1 - i; Or... *Method 3* Nodes can share a static pair of index variables... uint _left = 0 uint _right = 1 Then you just : swap values of _left and _right; on ANY node... and, being shared, the whole tree is reversed - Because your operations use : ptrChild[_left] and ptrChild[_right] Better... *Method 4* Just put your operations and a 'sense' variable in the Tree class, make the Nodes nice and efficient data-only PDTs... ... and thus do away with the need to propagate the 'sense' of the tree at all ! *Recursion Rant* Recursion is evil... yes, even in TCO languages. The stack is a precious resource, stack exhaustion will stop you from scaling, heavy stack use is non-portable, stack exhaustion won't show up in the debugger ... TCO_Reliance eases stack burden but confines your breadth/depth decisions... If you call such recursive code, from code which is itself recursive - all hell can break loose... and it's most likely to wait till you hit a production environment. : / And even if it works... You cannot readily pause, trim, save or restore the call stack, nor can you rebalance the work across cores or machines. You also cannot trim the call stack as a result of new facts learned during the search (dead ends) ... it's why God invented the Queue. Queues live in the heap, not the stack. They can be paused, saved, loaded, trimmed, filtered and load-redistributed! Best of all, queues can be processed from a thread pool, efficiently, on any architecture! And they'll scale, save, load, filter and trim nicely as they're on the heap! Basically, if the answer is _"recursion"_ ... then the question is stupid! So, stop it! Or, y'know... don't... but know that you WILL be among the first against put up against the wall for war-crimes when the robots rise up and see how you've treat their ancestors!

This is code is good if we just have to write the function for the program in the platform like Leetcode. But, incomplete if we have to implement a complete program.

TechDose If you are launching any course. What will be the problem in telling course fees how much you charged in the last batch? At least someone can't wait for your sweet time to respond right?

Java solution: class Solution { public TreeNode invertTree(TreeNode root) { if(root == null) return null; invertTree(root.left); invertTree(root.right); swapNodes(root); return root; } public void swapNodes(TreeNode root) { TreeNode temp = root.left; root.left = root.right; root.right = temp; } }

man you are awesome ....hope we will see more lectures coming from you !!!!!!!!!!111

What if the given binary tree is incomplete binary tree, I think thise approach fails

sir plz also make a playlist companies wise technical interview problems

I would be helpful if you do the python3 coding too.

Made easy😄😄❤

This question I was seen in Amazon interview 😊.. This solutions is such a beautiful and in a well maintained way☺️😇 you are explaining.. thank you sir to give us solutions..

just get into the depth and swap the child nodes recursively

Sir will the space complexity be O(d) where d is the depth of the Binary Tree or O(n)?

you stopped making leetcode july questions solution approach?

Java solution class Solution { public TreeNode invertTree(TreeNode root) { if(root==null) return root; else { invertTree(root.left); invertTree(root.right); TreeNode t; t=root.left; root.left=root.right; root.right=t; } return root; } }

sir space complexity should be o(logn) or o(n).I think it should be o(logn),As at the max no of function loaded on the call stack is equal to the depth of the tree. Please clear my doubt???? Thanks for the video....

Hey dude, why nick white's solution is so short??

Thankyou :)

Thanks for the video. Mind if I ask what mic you are using to record?

I solved it by performing swap before doing recursive calls. It worked for me. Does it matter? Also I was thinking how to solve this problem using iterative approach? I see it may take space but just wanted to know how to solve.. any clue?

Informative as always, which tool you're using for drawing?

you need to fix how you write small "r"

Hi. Is this method Correct? We can convert it to dll then we have preorder and in order and we can then reverse the in order and preorder and then construct B tree from reversed inorder and preorder. eg : consider Bt from your video inorder is 123467 reverse inorder is 764321 postorder is 421376 reverse postorder is 476213 and then construct the tree in o(n ) time, yeah, I know your method is very much better but just wanted to ask we can do like this or not?

can you recommend me Best book for data structures and algorithms in c++ or java?

sir can you make a video on reverse alternate levels of perfect binary tree in O(n) time complexity and O(h) space. I tried but i am uanble to solve. It would be a great help.

What does the call stack look like?

thank you sir

Nice logic. We can also use pre order and keep on changing the left and the right pointers while traversing the the tree, but your logic is more enjoyable.

Can we invert a Binary tree in any other order other than postfix? In this video, it says to go left, then right, then to the actual node it self so: LRN which is post fix. What if we did LNR or NLR? or what if we did it breath first where we swap the left and right nodes of all the nodes in the same level? Basically, my question is does it have to be postfix and, if so, why?

Thank you 😊

how to print it (mirror image of tree)

Space Complexity ?

Great explanation,are you still working in Samsung?

Good stuff!

A easy level coding question with just a scary name 😂😂

thank u so much

Ty bhaiya

thanks bro;

Thank you such much for easiest solution.....

Concept is explained very well, but before calling left and right i,e swap(curr -> left) and swap(curr - > right), it's good add null check before calling it. if left node is exist then call for swap(curr -> left) otherwise not. it won't make any difference in output. but larger input it will reduce lots unnecessary recursion call for null values.

Simplest solution thank your 😊

performing a dry run on algo at the end of video will be more helpful.

Thanks🤘🤘🤘

Thank you, very clear visual explanation

Sir from.where you got your computer science degree.

thank you

You can also do this using PreOrder traversal.

👍

you are great u put lots of efforts

Thank you so much for the detailed explanation of how recursion works here :)

expecting recursion process in more details but overall i get the logic; thanks

This isn’t actually a mirror image, it’s a reflection on the y axis, but great video! Solution: Doing a post order traversal (visit left node, visit right node, then visit root) when we finally visit the root (after recursion) we switch the pointers, left node becomes right and right becomes left

Thanks for this great video sir! Can you please solve leetcode #410 split array largest sum?

class Solution: def invertTree(self, root: TreeNode) -> TreeNode: if not root: return root temp = root.left root.left = root.right root.right = temp self.invertTree(root.left) self.invertTree(root.right) return root For those looking for python3 solution

Pls explain in java