Same Tree - Leetcode 100 - Python

[@NeetCode]

🌳🌲 Tree Playlist: kzbin.info/www/bejne/hZ-2n2WOerZng7s

[@jameshamilton3484]

Fantastic! I was just thinking that I'd like to focus on this area a while to get to grips with it. This pinned link saved me time, thank you.

[@dineshkumarkb1372]

For all Tree problems, could you also please upload the iterative approaches if possible?

[@dmitributorchin3658]

The only thing that you should mention always when discussing a recursive solution is a possibility of a stack overflow. In this exact problem this is not an issue because it's mentioned there could be maximum 100 elements in a tree. But if you fail to ask for a maximum possible number of elements in a data structure and you implement a recursive solution in an interview, you can expect to lose some points.

[@rainneskye527]

good point!

[@Lulit999]

What do I have to do If I was told that there is no maximum possible number of elements? Why it is only up to recursive solution?

[@Babe_Chinwendum]

@@Lulit999 Yeah I would like to know as well

[@tomrobinson5981]

@@Lulit999​ You can do an iterative solution (I did iterative BFS for this problem and it gives the same big O).

[@haha-hs7yf]

When does stack overflow happen? Does it happen when there are endless nodes and the function can't be stopped?

[@nero9985]

A question like this makes me feel like a tree master lol, I'd pray to get asked this one on an interview

[@romelpascua]

Your videos have been helping me so much. We both use Python and your explanations are very clear so thank you!

[@pauljones9150]

He gets so excited it's contagious

[@DrOvenProofStorm]

top notch youtube channel for real dude. Your explanations and organization of these videos are 👌.Keep up the good work!

[@TenzDelek]

have never touch upon tree topic so when i first saw the question input, my mind immediately went on the solution of array which somehow works. just a one liner. return str(q)==str(p).

[@mahdiranjbar3569]

In the worst case, where the two trees are identical, the runtime complexity is O(n), where n is the number of nodes in the trees.

[@rafik1968]

I think i am stupid a little bit, i used an approach to get the list of nodes of the first tree and the second tree using DFS or BFS and compare them, and to maintain the structure of the tree i inserted null to differentiate between different trees and the solution is time efficient but yours is really great and simple and have an average run time much more faster since it checks the condition each time so it can detect the False early.Thank u

[@kingfriizy5707]

this approach isn't stupid at all. its a pretty intuitive solution its just not the most space efficient

[@YashPratap7]

Wow man. That was so much easier to understand than any of the discussions on the problem itself

[@raviteja987]

isnt the time complexity is Order of min(p,q)?

[@HamzaYehia44]

I think so

[@MrMichalXXL]

actually a super easy explanation that makes the problem almost trivial

[@rainneskye527]

The code is simpler than I expected lol. Great work!

[@f-s_interpreter]

class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: return str(p) == str(q)

[@fahadhayat_]

Neetcode is the real plug!

[@zeyadali3379]

I guess the complexity here will be O(min(p,q)), as you will return false once you find that they are not identical, yes we are traversing at the same time, but we don't use more time traversing the other tree.

[@БорисБорсук]

i think the same

[@floatingfortress721]

Thanks, I found this video to be helpful in arriving at a recursive solution :)

[@vishalgadhvi]

one of the best explanation for this question over youtube. ✨

[@mohamedantar1249]

love your great explanation

[@xxRAP13Rxx]

Great video! Isn't the time complexity O(min(P,Q)) where we quit as soon as the smaller tree is deemed unequal to the bigger tree?

[@baltazar1106]

Yes but in interviews you answer the time complexity in worst case scenario, so in this case, worst case scenario is going through all nodes in both trees so O(p + q)

[@yeahiasarker7251]

man you code like a pro

[@adilismail3593]

Easiest explanation. Love ur videos.

[@Oliver-nt8pw]

It is kind of unclear to me if space complexity of DFS is O(M+N) because leetcode editorial claims O(M*N) thats a big difference.

[@Techgether]

1. Why isnt the time complexity O(p -(p-q)) since each of the function call will involve p and q together? - In the event where p has deeper depth than q - it will be O(p -(p-q)) since we will stop when reached the end of q - And in the event where p has lesser depth then q - it will be O(p) since we reached the end of p and returned. Thus, taking the worst case so should be O(p -(p-q))? 2. Instead of return(fx and fx), mine is: return False if not self.isSameTree(p.left, q.left) else self.isSameTree(p.right, q.right) - this should be more efficient since if left nodes comparison are not equal then it will reach end of recursion earlier?

[@SOMESHKHANDELIA]

Created a string representation of both trees p and q using current level information of a node and whether current node is in left or right subtree of parent. Then compared the two strings: class Solution { public: void get_string_rep(TreeNode* root, int curr_level, string &tree_str){ if(root == nullptr){ return; } else{ tree_str += to_string(root->val); tree_str += to_string(curr_level); if(root->left != nullptr){ tree_str += "L"; get_string_rep(root->left, curr_level+1, tree_str); } if(root->right != nullptr){ tree_str += "R"; get_string_rep(root->right, curr_level+1, tree_str); } } } bool isSameTree(TreeNode* p, TreeNode* q) { string tree_str_p = ""; get_string_rep(p, 0, tree_str_p); string tree_str_q = ""; get_string_rep(q, 0, tree_str_q); // cout

[@dolphinextreme48]

The BFS solution is more effective, using two queues. Recursion has too much overhead.

[@tomerva22]

O(min(p,q)) since u return false early

[@ishank7239]

Cleaner code: def isSame (p, q): if(p==None or q==None): return (p==q) return (p.val==q.val and self.isSame(p.left,q.left) and self.isSame(p.right,q.right))

[@robwalsh3858]

This is how I did it. The base case conditionals are much cleaner this way.

[@juliarozanova8579]

Better to check p.val==q.val outside of the recursive step; if it returns false, you save yourself some computations!

[@prajjwaldubey5787]

class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: tree1=self.preOrder(p,[]) tree2=self.preOrder(q,[]) if(tree1==tree2): return True else: return False def preOrder(self,node,ans): if(not node): ans.append(None) return ans.append(node.val) self.preOrder(node.left,ans) self.preOrder(node.right,ans) return ans I have done this

[@GroveCleve]

when i tried to set this up in a code editor I got an error on the "if not p or not q or p.val != q.val" line saying p and q are ints (likely on the second time through). I guess my question is how does the return line self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) work with the .left and .right values for p and q being ints? I was able to get it to work if I altered "if not p and not q" to "if (not p and not q) or p == q" but that doesn't seem necessary for leetcode to pass it (though it does still pass). thank you for the help and these videos have been so helpful.

[@anwarmohammad5795]

bro in the condition if not p or not q or p.val != q.val: consider this situation: if p is null and q is not null then q.val is not valid right..... so is it not better if we separate p.val != q.val....

[@oogieboogie7028]

The first condition: (if not node1 and not node2) will return True if both nodes are None. The second condition: (if not node1 or not node2 or node1.val != node2.val) evaluates only those cases where either one of the nodes is None or both of them have values. Now here is how python evaluates this 'OR' condition: The condition can be broken down into three parts: If any one of them evaluates to True it'll return False if not node1: if this evaluates to True, it returns False if not node2: if True return False So the (node1.val != node2.val) will only be evaluated if both of the previous conditions are False. i.e., if both nodes have values.

[@draugno7]

I am confused as to why returning early as in the commented section below showed worse memory performance (I guess it has to do with inputs Leetcode provided): public boolean isSameTree(TreeNode a, TreeNode b) { if (a == null && b == null) return true; if (a == null || b == null) return false; if (a.val != b.val) return false; return isSameTree(a.left, b.left) && isSameTree(a.right, b.right); /* OR instead of the line above: if (isSameTree(a.left, b.left) == false) return false; if (isSameTree(a.right, b.right) == false) return false; return true; */ }

[@TravelToEscape]

Thanks for the explanation. What is the use of "Self" and how do we know if its checking every node in the tree.

[@Senzatie160]

Self is just python syntax, nothing interesting. In JavaScript it would be isSameTree(x.left, x.right);

[@hamoodhabibi7026]

every time you do recursion your like taking a snapshot or a checkpoint for every node in the tree. Then when you return or finished all the code in the current checkpoint you come back to the original first executed code (main branch) which will now have all the values updated (every node checked)

[@aishwaryaranghar3385]

Amazing Explanation

[@sipwhitemocha]

Hello, so for 4:18 where the complexity is O( p + q), is that O(n) or considered O(1)?

[@symbol767]

Thanks man, liked.

[@kirillzlobin7135]

Ammmazing. Thank you very much

[@KANISHKSAHUSIME]

you are saving my life bro

[@moDefrawy]

Thanks And keep it on

[@Apoorvpandey]

Very helpful!

[@nikhilgoyal007]

thanks! If the TreeNode class is commented, how are p, q able to take on left, right properties (and be set as type TreeNode?).

[@davidmontes5989]

The commented out code is just the public documentation of the TreeNode API. The implementation of the TreeNode is private and not available to us but works on LeetCode's servers.

[@leeroymlg4692]

that's not the real code for the TreeNode class. That's just there to tell us what the code looks like so we know what class variables we can use

[@minciNashu]

what about checking pairs of nodes on each level for equality with BFS ?

[@tomrobinson5981]

This is what I did - iterative BFS. It gives you same time and space performance without the risk of stack overflow, however, as another commenter has mentioned, I think the real brownie points would come from asking the interviewer the max number of elements in a tree and making THEM aware that you're taking that into consideration.

[@KRABSTIK]

Why was it under BFS in leetcode?

[@sayanghosh6996]

the code can be cleaned up a bit, the and & or thing is redundant, just do it like this: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: if not p or not q: return p == q return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

[@Poppinthepagne]

i dont understand how self.isSameTree(q.left, p.right) compares that they are same? there is no != or == sign

[@CostaKazistov]

Legend, mate👍

[@brodoswaggins7870]

Meanwhile in JavaScript: return JSON.stringify(p) === JSON.stringify(q)

[@da_winraja9740]

is tree different from a regular list?

[@dumbfailurekms]

Iterative version can be achieved with the following concept in mind: Traverse both trees simultaneously and return False on certain checks. Keep in mind, that two nonidentical trees can have the same traversal output. So there will be another check in addition to comparing values (same concept in this video)

[@sanooosai]

great thank you

[@hyungminkim6664]

Thanks for the vid! Anyone knows what the space complexity will be?

[@sameersahu3987]

O(1) cause we didn't defined any additional variables

[@magicinternetmoney8715]

@@sameersahu3987 this is wrong... It's a recursive function and so there will be some implicit memory usage from the function's call stack. We are recursing on the left subtrees of p and q, and also the right subtrees of p and q. At any given point during execution, the call stack will either be on the left subtrees or the right subtrees, either way the worst case is O(p + q) if p and q are both completely unbalanced trees.

[@tonynguyen6124]

@@magicinternetmoney8715 Thanks for this. I did my own implementation with BFS using a queue and was wondering why it had similar memory usage to this solution.

[@yskida5]

@@magicinternetmoney8715 do you mean if they are both perfectly balanced?

[@stan8851]

Nice, thank you

[@adamgerber7824]

LOL I got "Beats 100%" on LC with this

[@overPowerPenguin]

As usual, I've over complicated when tried to solve it 😅 .

[@whonayem01]

Thanks.

[@kennethaidoo361]

Easiest tree question

[@hippohhua]

basically return p==q :)

[@tyler_the_explorer8270]

why is my base case wrong if p and q: return p.val == q.val elif not p and not q : return True else: return False

[@expansivegymnast1020]

Waaay easier to solve this after listening to someone talk it through

[@mingjunma293]

why if I change the line 11 into " if not p and q: return False if p and not q: return False" is wrong?

[@Aret24Official]

That's because there is a condition which checks if "not p and not q". It returns true if it works. Now we do the "not p or not q" thing, which you might now works if : 1) p and not q; 2) not p and q: 3) not p and not q. But since we already know what happens with "not p and not q", there is nothing wrong with writing "not p or not q", as it will do just the thing we want. But your variant is not wrong tho, just not as a efficient.

[@dkdlife6210]

Why dont we use the solution: DFS traversal 2 trees and compare them. I think both solutions got the same Time Complexity and Space complexity but we already know the DFS traversal and we can apply it here instead of another recursive function. def dfs(root): if root is None: return ['N'] res = [] res+= [root.val] res+= dfs(root.left) res+= dfs(root.right) return res class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: return dfs(p)==dfs(q)

[@tomrobinson5981]

This is adding a list comparison which would be worst case O(p) onto two full traversals (always O(p + q)) giving you O(2p + q) whereas the video solution is worst case O(p + q).

[@ahmedamr1124]

i solved it with queue

[@noelcovarrubias7490]

Is this how we are supposed to solve tree problems? By first thinking of all the edge cases, looking at the sub-problems and then figuring out the recursive steps ?

[@hamoodhabibi7026]

Well when I first saw this problem I immediately thought oh it's a tree problem and we can use some sort of traversal method. I chose DFS, and now from there I drew example pictures of the tree to see and scope out any patterns or "SUBPROBLEMS" I can find. Now before you even think about coding the last main part you must do is consider all the base cases OR in other words how your recursion is going to end and what values your going to return in each state. After you get your base case you already found the code structure without coding lol :D

[@ItzGanked]

neetcode is based

[@nikhileswarareddy3182]

The code explained is Failing for [0,-5] [0,-8]

[@shaharrefaelshoshany9442]

best ever

[@mahanirvaantantra]

They call this easy but it is difficult to understand

[@DanhWasHere]

Hey looks like the LeetCode problem link is incorrect: it's using convert sorted array to BST

[@NeetCode]

Thanks for letting me know, Fixed!

[@Nobody-df7vn]

why is this depth first search?

[@hamoodhabibi7026]

It's just one of the ways of doing recursion to traversing a tree

[@tonyiommisg]

Could you just say 'not p xor not q'? In my mind that makes more sense

[@PippyPappyPatterson]

ಠ_ಠ

[@PippyPappyPatterson]

`xor` doesn't exist in Python, but you could do this as `bool(p) ^ bool(q)`

[@erik-sandberg]

ಠ_ಠ

[@philandros3195]

I don't think I understand how the tree works. In the first test case the trees are q = [1, 2, 3] and p = [1, 2, 3] and if I write: return q.val == p.val and q.left == p.left and q.right == p.right, the output is False??? Also if I try just return q (for science), I would expect the output to be the tree [1,2,3], but instead the output is True?? What the fuck. How do these damn trees work?!?

[@mightyprogrammer2899]

from collections import deque class Node(object): def __init__(self, value): self.value = value self.left = None self.right = None class BinaryTree(object): def __init__(self, root): self.root = Node(root) def print_result(self, traversal_type, tree_2): if traversal_type == "is_same_tree_recursive": return self.isSameTree_DFS_recursive(self.root, tree_2.root) if traversal_type == "is_same_tree_iterative": return self.isSameTree_BFS_iterative(self.root, tree2.root) else: print("Depth type " + str(traversal_type) + " is not supported.") return False def isSameTree_DFS_recursive(self, p, q): if not p and not q: return True if not p or not q or p.value != q.value: return False return (self.isSameTree_DFS_recursive(p.left, q.left) and self.isSameTree_DFS_recursive(p.right, q.right)) def isSameTree_BFS_iterative(self, p, q): queue = deque([(p, q)]) while queue: node_p, node_q = queue.popleft() if not node_p and not node_q: continue if not node_p or not node_q or node_p.value != node_q.value: return False queue.append((node_p.left, node_q.left)) queue.append((node_p.right, node_q.right)) return True if __name__ == "__main__": tree1 = BinaryTree(1) tree1.root.left = Node(2) tree1.root.right = Node(3) tree2 = BinaryTree(1) tree2.root.left = Node(2) tree2.root.right = Node(0) X = tree1.print_result("is_same_tree_recursive", tree2) print(X) Y = tree1.print_result("is_same_tree_iterative", tree2) print(X)

[@amirhossein1108]

I am pretty sure that your code does not work

[@NeetCode]

I just ran it and it does.

[@neighboroldwang]

I still don't get why does (self.isSameTree(p.left, q.left)) works. Could someone explain a bit?