🌳🌲 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?
@dmitributorchin36582 жыл бұрын
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.
@rainneskye5272 жыл бұрын
good point!
@Lulit9992 жыл бұрын
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_Chinwendum2 жыл бұрын
@@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?
@nero99852 жыл бұрын
A question like this makes me feel like a tree master lol, I'd pray to get asked this one on an interview
@romelpascua3 жыл бұрын
Your videos have been helping me so much. We both use Python and your explanations are very clear so thank you!
@pauljones91502 жыл бұрын
He gets so excited it's contagious
@DrOvenProofStorm3 жыл бұрын
top notch youtube channel for real dude. Your explanations and organization of these videos are 👌.Keep up the good work!
@TenzDelek8 ай бұрын
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).
@mahdiranjbar35693 ай бұрын
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.
@rafik196811 ай бұрын
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
@kingfriizy570710 ай бұрын
this approach isn't stupid at all. its a pretty intuitive solution its just not the most space efficient
@YashPratap72 жыл бұрын
Wow man. That was so much easier to understand than any of the discussions on the problem itself
@raviteja9872 жыл бұрын
isnt the time complexity is Order of min(p,q)?
@HamzaYehia442 жыл бұрын
I think so
@MrMichalXXL6 ай бұрын
actually a super easy explanation that makes the problem almost trivial
@rainneskye5272 жыл бұрын
The code is simpler than I expected lol. Great work!
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.
@БорисБорсук10 ай бұрын
i think the same
@floatingfortress72110 ай бұрын
Thanks, I found this video to be helpful in arriving at a recursive solution :)
@vishalgadhvi2 жыл бұрын
one of the best explanation for this question over youtube. ✨
@mohamedantar124927 күн бұрын
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?
@baltazar11065 ай бұрын
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)
@yeahiasarker72512 жыл бұрын
man you code like a pro
@adilismail3593 Жыл бұрын
Easiest explanation. Love ur videos.
@Oliver-nt8pw11 ай бұрын
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.
@Techgether4 ай бұрын
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?
@SOMESHKHANDELIA4 ай бұрын
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
@dolphinextreme489 ай бұрын
The BFS solution is more effective, using two queues. Recursion has too much overhead.
@tomerva222 жыл бұрын
O(min(p,q)) since u return false early
@ishank72392 жыл бұрын
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))
@robwalsh38582 жыл бұрын
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
@GroveCleve2 жыл бұрын
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.
@anwarmohammad57952 жыл бұрын
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.
@draugno77 күн бұрын
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; */ }
@TravelToEscape2 жыл бұрын
Thanks for the explanation. What is the use of "Self" and how do we know if its checking every node in the tree.
@Senzatie1602 жыл бұрын
Self is just python syntax, nothing interesting. In JavaScript it would be isSameTree(x.left, x.right);
@hamoodhabibi70262 жыл бұрын
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)
@aishwaryaranghar33853 жыл бұрын
Amazing Explanation
@sipwhitemocha8 ай бұрын
Hello, so for 4:18 where the complexity is O( p + q), is that O(n) or considered O(1)?
@symbol7672 жыл бұрын
Thanks man, liked.
@kirillzlobin7135 Жыл бұрын
Ammmazing. Thank you very much
@KANISHKSAHUSIME2 жыл бұрын
you are saving my life bro
@moDefrawy2 жыл бұрын
Thanks And keep it on
@Apoorvpandey2 жыл бұрын
Very helpful!
@nikhilgoyal0072 жыл бұрын
thanks! If the TreeNode class is commented, how are p, q able to take on left, right properties (and be set as type TreeNode?).
@davidmontes59892 жыл бұрын
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
@minciNashu2 жыл бұрын
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.
@KRABSTIK7 күн бұрын
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)
@Poppinthepagne2 жыл бұрын
i dont understand how self.isSameTree(q.left, p.right) compares that they are same? there is no != or == sign
@CostaKazistov2 жыл бұрын
Legend, mate👍
@brodoswaggins78704 ай бұрын
Meanwhile in JavaScript: return JSON.stringify(p) === JSON.stringify(q)
@da_winraja97402 жыл бұрын
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)
@sanooosai9 ай бұрын
great thank you
@hyungminkim66642 жыл бұрын
Thanks for the vid! Anyone knows what the space complexity will be?
@sameersahu39872 жыл бұрын
O(1) cause we didn't defined any additional variables
@magicinternetmoney87152 жыл бұрын
@@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.
@tonynguyen61242 жыл бұрын
@@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.
@yskida52 жыл бұрын
@@magicinternetmoney8715 do you mean if they are both perfectly balanced?
@stan88513 жыл бұрын
Nice, thank you
@adamgerber782414 күн бұрын
LOL I got "Beats 100%" on LC with this
@overPowerPenguin Жыл бұрын
As usual, I've over complicated when tried to solve it 😅 .
@whonayem012 жыл бұрын
Thanks.
@kennethaidoo361 Жыл бұрын
Easiest tree question
@hippohhua2 жыл бұрын
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
@mingjunma2933 жыл бұрын
why if I change the line 11 into " if not p and q: return False if p and not q: return False" is wrong?
@Aret24Official2 жыл бұрын
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.
@dkdlife62102 жыл бұрын
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
@noelcovarrubias74902 жыл бұрын
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 ?
@hamoodhabibi70262 жыл бұрын
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
@ItzGanked2 жыл бұрын
neetcode is based
@nikhileswarareddy31822 жыл бұрын
The code explained is Failing for [0,-5] [0,-8]
@shaharrefaelshoshany94423 жыл бұрын
best ever
@mahanirvaantantra6 ай бұрын
They call this easy but it is difficult to understand
@DanhWasHere3 жыл бұрын
Hey looks like the LeetCode problem link is incorrect: it's using convert sorted array to BST
@NeetCode3 жыл бұрын
Thanks for letting me know, Fixed!
@Nobody-df7vn2 жыл бұрын
why is this depth first search?
@hamoodhabibi70262 жыл бұрын
It's just one of the ways of doing recursion to traversing a tree
@tonyiommisg3 жыл бұрын
Could you just say 'not p xor not q'? In my mind that makes more sense
@PippyPappyPatterson2 жыл бұрын
ಠ_ಠ
@PippyPappyPatterson2 жыл бұрын
`xor` doesn't exist in Python, but you could do this as `bool(p) ^ bool(q)`
@erik-sandberg2 жыл бұрын
ಠ_ಠ
@philandros31958 ай бұрын
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.
@neighboroldwang5 ай бұрын
I still don't get why does (self.isSameTree(p.left, q.left)) works. Could someone explain a bit?