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?

[@pauljones9150]

He gets so excited it's contagious

[@nero9985]

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

[@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).

[@romelpascua]

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

[@DrOvenProofStorm]

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

[@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.

[@YashPratap7]

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

[@f-s_interpreter]

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

[@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

[@MrMichalXXL]

actually a super easy explanation that makes the problem almost trivial

[@raviteja987]

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

[@HamzaYehia44]

I think so

[@rainneskye527]

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

[@fahadhayat_]

Neetcode is the real plug!

[@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

[@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

[@adilismail3593]

Easiest explanation. Love ur videos.

[@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!

[@yeahiasarker7251]

man you code like a pro

[@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)

[@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

[@tomerva22]

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

[@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

[@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.

[@dolphinextreme48]

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

[@sipwhitemocha]

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

[@kirillzlobin7135]

Ammmazing. Thank you very much

[@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.

[@Poppinthepagne]

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

[@aishwaryaranghar3385]

Amazing Explanation

[@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)

[@moDefrawy]

Thanks And keep it on

[@Apoorvpandey]

Very 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.

[@KANISHKSAHUSIME]

you are saving my life bro

[@KRABSTIK]

Why was it under BFS in leetcode?

[@symbol767]

Thanks man, liked.

[@sanooosai]

great thank you

[@whonayem01]

Thanks.

[@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

[@stan8851]

Nice, thank you

[@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.

[@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?

[@da_winraja9740]

is tree different from a regular list?

[@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; */ }

[@CostaKazistov]

Legend, mate👍

[@souljarohill8795]

Not a hard problem but I couldnt solve the last 3 test cases due to the additions of Nulls in the input. edit: Was able to solve my way using a in order traversal. At first I did a pre order. Why I wonder?

[@brodoswaggins7870]

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

[@shaharrefaelshoshany9442]

best ever

[@hippohhua]

basically return p==q :)

[@adamgerber7824]

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

[@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

[@overPowerPenguin]

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

[@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.

[@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)

[@expansivegymnast1020]

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

[@ahmedamr1124]

i solved it with queue

[@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)

[@kennethaidoo361]

Easiest tree question

[@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

[@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).

[@ItzGanked]

neetcode is based

[@nikhileswarareddy3182]

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

[@Nobody-df7vn]

why is this depth first search?

[@hamoodhabibi7026]

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

[@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!

[@mahanirvaantantra]

They call this easy but it is difficult to understand

[@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)

[@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?!?

[@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?