Invert Binary Tree - Depth First Search - Leetcode 226

0:00 - Read the problem
2:05 - Coding Explanation

leetcode 226

#invert #tree #python

[scofield]

That’s so much easier than what I thought the problem was asking. When I heard “invert a binary tree” I thought it meant to pick one of the deepest child nodes and make it the new root node, rebuilding the tree inverted vertically.

[monicawang]

No need to store in temp:

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return root

[BiranchiNarayanNayak]

The swapping can be done by : root.left, root.right = root.right, root.left

[Rahul-wvqc]

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

[MaxFung]

makes me feel super cool that i solved this first try. i was feeling really down on my interview skills, but this gave me a great boost of confidence knowing max howell didn't solve it in his interview - who knows what leetcode easy i might fail in the future, but we're all learning and doing our best!!!

[petarJK]

Very good video. Very simple problem once you understand tree traversals and recursion. Just started learning about trees yesterday. Very interesting subject. I'm learning Java, but the code for this problem is basically the same, minus the syntax.

[AIPlayerrrr]

I love your videos. You are very good at explaining things. Thanks a lot for the content!

[EricProgramming]

I was about to make a video on this as well, but it seems like you did a great job at it. 👍

class Solution {
public TreeNode invertTree(TreeNode root) {
//Base case
if(root == null) return null;

if(root.left == null && root.right == null) return root;

//Revert the left subtree
TreeNode left = invertTree(root.left);

//Revert the right subtree
TreeNode right = invertTree(root.right);

//Revert current tree
root.right = left;
root.left = right;

return root;
}
}

[christopherperezlebron]

time -> O(N) b/c we touch each node once
space -> O(h) where h is the height of the binary tree (Which at worst is n but in general the relationship between height and number of nodes can be logarithmic or linear) b/c that is our longest stack will get.

[samsun]

I found iterative way is easier to understand.
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return root
stack = [root]
while stack:
curr = stack.pop()
curr.left, curr.right = curr.right, curr.left
if curr.left:
stack.append(curr.left)
if curr.right:
stack.append(curr.right)
return root

[briansigilai]

For my Java comrades:

class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null) return root;

TreeNode hold = root.left;
root.left = root.right;
root.right = hold;

invertTree(root.left);
invertTree(root.right);

return root;
}
}

[spiceybyte]

Time complexity = O(n) because you have to traverse every node at least once
Space complexity = O(logn) if tree is balanced or worst case O(n) unbalanced height of the tree (maximum size of the call stack)

[alistartop]

What would be the time complexity of this code? I struggle to find it for recursion algos in general - any tips? Thanks always!

[christopherchiu]

felt stupid because i thought that we had to run the algo on a list and not on the provided binary object. thank you for your help as always

[harunguven]

Thank you, this is really a good problem for beginners, especially ones trying to learn recursion.

[michaelyao]

This is way better than the official answer! Thumb up

[protodimbo]

thanks for the vid. Whats the time and space complexities?

[dumbfailurekms]

Iterative version was a good exercise that truly strengthened my understanding of trees and problems related to trees.

I got the idea to do an iterative version from Neetcode providing both recursive and iterative solutions to other problems.

Here's the solution in case anyone wants it.

stack = []
cur = root
stack.append(cur) #this was important, it's also the reason why adding "or cur" to the loop results in a funny outcome
while stack:
if not cur:
cur = stack.pop()
else:
stack.append(cur.left)
stack.append(cur.right)
tmp = cur.left
cur.left = cur.right
cur.right = tmp
cur = stack.pop()

return root

[midasredblade]

in python, you need not go through the trouble of assigning a tmp value, try
n.left, n.right = n.right, n.left
due to being in the same line, python uses a tmp internally maybe and swaps the value without you having to go through all that trouble

however, 1. n.left = n.right
2. n.right = n.left
doesnt work

[hmatpin]

Hello: I don't understand why the leet code input for the test cases is an array of numbers and not an object with nodes that have the left and right attributes. The test cases do show an SVG diagram of the tree. Should the user assume that once the code runs the platform turns the array into the tree structure and then passes it to the function being tested before the test runs? This question is mostly understanding the platform.