Same Tree - Leetcode 100 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Dynamic Programming Playlist: • House Robber - Leetco...
Tree Playlist: • Invert Binary Tree - D...
Linked List Playlist: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/same-bin...
0:00 - Read the problem
1:15 - Drawing Explanation
4:27 - Coding Explanation
leetcode 100
This question was identified as an interview question from here: github.com/xizhengszhang/Leet...
#same #tree #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

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

[@romelpascua]

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

[@YashPratap7]

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

[@DrOvenProofStorm]

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

[@nero9985]

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

[@pauljones9150]

He gets so excited it's contagious

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

[@vishalgadhvi]

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

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

[@adilismail3593]

Easiest explanation. Love ur videos.

[@aishwaryaranghar3385]

Amazing Explanation

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

[@Apoorvpandey]

Very helpful!

[@yeahiasarker7251]

man you code like a pro

[@kirillzlobin7135]

Ammmazing. Thank you very much

[@MrMichalXXL]

actually a super easy explanation that makes the problem almost trivial

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

[@symbol767]

Thanks man, liked.

[@CostaKazistov]

Legend, mate👍

[@moDefrawy]

Thanks And keep it on

[@stan8851]

Nice, thank you

[@raviteja987]

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

[@HamzaYehia44]

I think so

[@sipwhitemocha]

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

[@KANISHKSAHUSIME]

you are saving my life bro

[@sanooosai]

great thank you

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

[@tomerva22]

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

[@shaharrefaelshoshany9442]

best ever

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

[@whonayem01]

Thanks.

[@Poppinthepagne]

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

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

[@user-rj9xz1rv2p]

i think the same

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

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

[@dolphinextreme48]

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

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

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

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

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

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

[@hippohhua]

basically return p==q :)

[@overPowerPenguin]

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

[@f-s_interpreter]

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

[@expansivegymnast1020]

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

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

[@kennethaidoo361]

Easiest tree question

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

[@ItzGanked]

neetcode is based

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

[@Nobody-df7vn]

why is this depth first search?

[@hamoodhabibi7026]

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

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

[@nikhileswarareddy3182]

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

[@mahanirvaantantra]

They call this easy but it is difficult to understand

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

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

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

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

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

ಠ_ಠ

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