Subtree of Another Tree - Leetcode 572 - Python

[@vert_sr]

Please note that you are saving my career. Thank you for being a hero

[@trh786fed]

Hey it's been 2 years, what did you achieve ?

[@pinakeekaushik4311]

@@trh786fed 😂

[@johnlocke4695]

Your channel is like a cheatcode to leetcode. Thank you neetcode!!

[@shubhamthanki1896]

Absolutely love your channel. To the time you feel low or demotivated ever to continue this channel, I'll say only one thing, what you give is what you get back, and you're giving happiness to all of us in abundance, so you'll definitely get it back.

[@milesba4]

Great explanation! One small optimization is to check if the root's value and the subRoot's value are the same before we call the isSame function on the trees. Because if the values aren't initially the same, then we know one can't be a subtree of the other. Example: def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: #iterate through tree def isSame(root,subroot): if not root and not subroot: return True elif not root or not subroot: return False else: if root.val==subroot.val: return (isSame(root.left,subroot.left) and isSame(root.right,subroot.right)) #if main tree and subtree are both null, return True - subsets of eachother if not root and not subRoot: return True #if main tree is null, return False - nothing can be a subset of a null tree other than a null tree if not root: return False #if we find two values that are the same, then check if the subtrees are the same if root.val == subRoot.val and isSame(root,subRoot):

[@ejmurc]

His code already does this. s.val == t.val is labeled in his conditional in the recursive function.

[@IwoGda]

@@ejmurc His code is doing it in function, but @milesba4 code is doing it before calling function. In python for example "if cond1 and cond2" and cond1 is false then cond2 isn't checked.

[@tb8588]

the complexity of this problem should be a medium - def not an easy one lol

[@NeetCode]

Agree!

[@NorthernlionLP]

It's easy once you do Leetcode #100 (same tree) or Leetcode #101 (symmetric tree) first. I would recommend solving those two before coming to this one.

[@devonflowers7156]

Lol agree but funny bc if you go into the comments on ANY easy tree problem in LC you see at least 10 “should be medium” lol

[@DataScienceGuy]

@@devonflowers7156 I think that if you need to solve other easy problem inside (same tree) to solve this problem - it is medium )

[@recneps1000]

These videos are super concise and really helpful. Thank you.

[@apgapgapgapg]

I just did a traversal (e.g., preorder) of each tree separately, concatenating the values as a string representations, with each node prefixed and postfixed with a symbol (e.g., '-'). Include 'None' nodes in the string representation. Then all you do is check if the string representation of the subtree is 'in' the string representation of the tree. Ends up being O(N + M) time complexity (although requires additional memory for the strings.

[@abpsoluciones]

Same here!

[@tomonkysinatree]

I saw the trick in what I needed to do for the recursion this time in the code before you explained. Slowly getting better. Think you saved me a lot of time by going through the edge cases in the explanation

[@md-ayaz]

man, you are the saviour. I am unemployed and preparing. Thank you so much man!

[@hugovinhal3576]

The first if statement is not necessary. You never get to a null case on the subRoot since you never change its value.

[@electric336]

But you still need the check incase subRoot is null to begin with.

[@princezuko7073]

@@electric336 subRoot won't be null since it is given in the testcase "'subRoot' to have 1

[@amynguy]

both if are not needed: This is enough: if sameTree: return True return root != null and (sametree(root.left,subtree) or sametree(root.right,subtree)

[@PippyPappyPatterson]

This solution's implementation is the easiest for me to bungle up out of all the tree problems.

[@andrewberumen]

Thanks for this! One issue I always come across is determining when a helper function may be necessary. Do you have any tips?

[@EricCycles]

Basically if you have some piece of logic that will be needed along the way to solve the main problem, then you want to define that logic in a helper. In this case, the main problem is whether tree t is a subtree of tree s, to answer this we need to know if there exists some tree within s that is equal to t. Since we need to know this for possibly every tree that starts at some node in S, it is easier to have it as a helper that we can call to at each step

[@ehm-wg8pd]

You could solve this with lower complexity by making it pre order traversal string and use pointers to check if both string have substrings O(M + N)

[@symbol767]

Thanks bro, I'm doing all your problems currently, solving it on my own first and comparing my answer to yours. Liked!

[@adityaprasad9734]

After watching the binary tree (de)serialization video, here's a O(s+t) solution: def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: if not root.left and not root.right and not subRoot.left and not subRoot.right: return root.val == subRoot.val def dfs(root): return f"{root.val},{dfs(root.left)},{dfs(root.right)}" if root else "N" return dfs(subRoot) in dfs(root) We check the first condition bc it might incorrectly return smth like 1 is in 11. Edit: "in" is not O(s+t) but O(st), would have to replace with KMP.

[@oskarhernandez5364]

It seems they've added new test cases I think. This solution seems not working anymore. Is the solution wrong or are the test cases incorrect?

[@ahmadbasyouni9173]

I am having same problem

[@mengdizheng1223]

the solution given here is by recursive DFS. like other videos, this can be solved by BFS with a queue to save the nodes on each level too . pretty fast .

[@Adunc67]

This. ^^ is the smart way to do it

[@nguyen-dev]

I am thinking about using hashcode and equals methods for the subtree. The equals method does exactly the isSameTree method. The most important of the hashcode is to reuse the calculated hash code of left subtree and right subtree for the parent node. So we only need to double check with equals method if hashcode is the equal. Assume hashcode method has 1% collision, equals method will need to run unnecessary one per 100 comparison.

[@christopherperezlebron2434]

this solution has time complexity O(n^2) and space complexity O(h) where h is the height of the tree [the height can vary from log n to n depending on the structure of the tree)

[@happypenguin236]

The number of nodes are guaranteed to be more than 1 for both root and subroot. The edge case where both is null does not need to be considered. Only the case where root becomes none while traversing should be the base case.

[@raghav5354]

do we need to know O(S + T) approach for interviews?

[@serpent2776]

For this problem specifically you don't need the if not t condition because we're given the subRoot always has one node in it. Not sure if that changed between this video and the problem now though.

[@roguenoir]

I struggled on this one for hours even though it was "easy" because I thought there was a solution that wasn't O(both trees' sizes multiplied)

[@jeffwei]

same

[@rohankamath794]

@@jeffwei How are you verified lmao

[@illu1na]

There is, you need to post order / in order both threes and compare two lists. O(max(S, T))

[@EE12345]

I notice that there are O(M+N) solutions available on the Leetcode site. Would this solution be acceptable in an interview or would they want the more optimal ones?

[@dominic6201]

the fact that it is not presented here shows that it is probably too difficult to come up with in most interviews? i am certainly not preparing it.

[@illu1na]

Not sure if O(S*T) would be the most efficient solution, Since if all nodes have the same numbers, the algorithm would effectively call sameTree() for all S nodes. I solved it by using postorder (In-order would also do fine) on both S and T and compare the list of these post order by using two pointers. It is much longer solution than the suggested one by Neetcode but the overall time and space complexity is O(max(S, T)). Neetcode also has the same space complexity due to recursion stack.

[@ashwanikumar415]

Can we take advantage of the fact that no values in binary tree can be repeated twice . So writing in JS(as i not aware of python) : function isSubtree(root, subRoot) { let tree = getAppropriateSubtree(root, subroot); // it will recursively check tree.val === subRoot.val . Once they are same , it will return root let isTreeSame = sameTree(tree, subtree); // now check if partial tree returned from above method is same as subTree return isTreeSame; }

[@The6thProgrammer]

Great video / solution as always. I took a slightly different approach with same time complexity that felt a bit more intuitive to me than recursing with isSubtree. I used a breadth first search on S and for each node I processed in S, I checked if the value of that node was equal to the root of T. If yes, I ran sameTree (which I implemented recursively similar to the solution provided). If sameTree returned True at any point, I ceased my BFS and returned True. Also note: the problem definition specifies that S and T will each have >= 1 node. So you don't need to actually check the edge cases that you check regarding S or T being completely null. Here's my code: class Solution { public: bool isSubtree(TreeNode* root, TreeNode* subRoot) { deque nodes { root }; bool subTree { false }; while (!nodes.empty()) { TreeNode* currNode { nodes.front() }; nodes.pop_front(); if (currNode->left != nullptr) { nodes.push_back(currNode->left); } if (currNode->right != nullptr) { nodes.push_back(currNode->right); } if (currNode->val == subRoot->val) { subTree = sameTree(currNode, subRoot); } if (subTree) { return subTree; } } return subTree; } bool sameTree(TreeNode* a, TreeNode* b) { if (a == nullptr && b == nullptr) { return true; } if (a == nullptr || b == nullptr || a->val != b->val) { return false; } return sameTree(a->left, b->left) && sameTree(a->right, b->right); } };

[@madanielmadaniel]

Thank you very much for a yet another detailed explanation 🎖- didn't have a chance to understand it by my own.

[@NeetCode]

Happy to help 🙂

[@vm1662]

Thanks NeetCode for the explanation. Leetcode has 2 more solutions apart from this. One is serialization then String pattern matching and second one is Tree Hash. Do interviewers really expect you to come up with the 2 other solutions or is the one presented here fine? Just curious on how to handle such questions during interviews :)

[@dhruvkhurana9235]

Thank you man - you're awesome for these videos

[@NeetCode]

Thank you so much!!

[@anishpahilajani4753]

What is Space complexity? I think its O(no. of root nodes * no. of subRoot nodes).

[@kewtomrao]

Reall "Neet" and concise explanation!

[@yahyaooo1]

Just discovered your channel, I f*cking love you man :') Thank you for sharing this with us poor plebs

[@NeetCode]

Thank you so much, I really appreciate it!!! :)

[@aaen9417]

super elegant explanation

[@wtcxdm]

since the t is always going to be checked on its root, isn't it unnecessary to have a case for t == null in isSubtree function?

[@focminging652]

hey man thanks for the help i just spent like 8 hours on this question your channel saved my life

[@mpalanipsbb]

GREAT explanation!

[@sangaharshitha9357]

thank you dude seriously I was stuck with this question and wasn't able to understand this question until u explained this thank youuu so much

[@freemanjiang]

The mutual recursion is genius

[@danyeun01]

in this problem would if self.sameTree(root, subRoot): return True be considered the base case as well?

[@debmalyakundu1342]

we can serialize the subtree and can check with every root in original tree while serializing from bottom? complexity is also good I guess

[@itachid]

Is checking if the subtree is not null really necessary as we are returning true (we are basically doing: if true, return true)? The code runs just fine without it or am I missing something crucial?

[@musicgotmelike9668]

Great video! I'm wondering if there are ways to avoid brute forcing this problem?:) Anyone any ideas?

[@mohamedantar1249]

wow, This is a wonderful explanation

[@orellavie6233]

how about Preorder traversal and In order traversal on both trees (pre order and in order together promising there is one match).,which is 2 * O(T1+T2), so O(T1+T2). Then, perform Rabin Karp on the 4 strings (2 for preorder, one a substr of the second, and 2 for the inorder). which is with good hash a O(t1+t2) in average (with collisions only t1*t2). Do you agree?

[@trillionman2105]

How exactly do you transition from having the string of the tree to in order and preorder to finding a match, is it simple? I did linear time preprocessing the heights of the nodes of the big tree.

[@swavida]

Hi! I tried to this question without the sameTree function but it was failing for the case such as this one: root = [1,1] subRoot = [1] How can it be done without the sameTree function?

[@jeielmosi]

You could use a hashmap and a id generator (incremental number for example). The key of a hashmap will be a string with the root.val and the ids of the left and right subtrees. The value of hashmap will be the id. This approach will solve in O(S+T) in time and O(T) in memory.

[@ReArNiDcOM]

Something I am having a hard time understanding: in the isSubtree function if we are recursively calling it then at some point we would call it on a node that has null children. ( in this example 5 has null children ) Those null children would then be put into one of the recursive calls ( return self.isSubtree(s.left,t) or self.isSubTree(s.right, t) ) and we would return False since they are null. This however would just mean we went down a path where the sub tree was not found we wouldn't necessarily want to return False which states it was not not found at all. Am I missing something or does my interpretation display valid confusion?

[@sourabhxp92]

Both the if statements on line 9 and 10 would check check if the node is not null

[@oliverduan1374]

Just maybe a stupid alternative solution: could we serialize both the trees and use "in" to see if t is a substring of s? I am talking about using python here

[@jointcc2]

I think the explanation could have been made clearer if he had pointed out that is tree helper function is used to compare the values between the two subtrees and the subtree function is used to traverse/visit each subtree, which then makes it O(s*t)

[@tesszheng4586]

or we can serialize both trees using preorder, then check whether string of parent tree contains string of child tree

[@VGBNDGRL]

Curious, why is this N*M time complexity? in the SameTree video, the time complexity is N+M. Can someone elaborate? My educated guess is that calling another recursive func inside of our recursive func would make this exponential.

[@ZSonnenblick]

For sameTree, you only have to go through each of the nodes a single time so O(N+M) just means checking every node of both trees. In this problem, you're not calling the sameTree function a single time. In the worst case you'd be calling it on every single node of the Tree. So for each node of tree youd have to once again check each node in subtree to see if they match. if that makes sense

[@liuashley4124]

great explanation!! but im just a little confused on why we return true if t == null, would t ever be null ?

[@Ynno2]

Not with the constraints given on the current Leetcode version of this problem, but an interviewer could always say it might be null in a slightly different version.

[@forceboxed]

Is COMPLEXITY REALLY O(S.T) ? 🧐 I think it is O(S.(S+T)) ✅ Why: 1. Note that complexity of `sameTree` is O(S+T) in the worst case (i.e. when `s` and `t` are same). 2. Now, consider the case that `sameTree` returns false for trees `s` and `t`. 3. Here, you are THEN recursing on the `isSubtree` (line #14) which AGAIN visits the nodes in `s` !!! 4. ** So, BASICALLY, we are calling `sameTree` for every node in `s` ** 5. This means the time complexity is O(S.(S+T)) What do people think?

[@Ynno2]

sameTree isn't O(S+T). Removing constant factors it's actually O(min(S, T)). It would only be O(S+T) if we were doing independent traversals of the two trees. Consider what happens when we have S with 1000 nodes and T with 0 nodes. You're saying we could do up to 1000+0=1000 iterations. It's impossible to do 1000, we immediately return `False` on the first invocation because of the `s and t` part of the if-condition. So, you could say it's O(S * min(S,T)). But that's equivalent to O(S * T) because: 1. S > T, then min(S,T) = T and it's equivalent to O(S * T) 2. S

[@jacobkorede2486]

Thanks neetcode❤

[@leetcodemonkey]

I really like this problem. Nice one

[@leetcodemonkey]

Almost 2 years later, revisiting this "easy" problem (as per leetcode), took me some time to understand the soln and writing the code 💀 Feeling sad that I couldn't solve this problem by myself this time 😭

[@dollyvishwakarma2]

Can anyone let me know, when is it better to define the helper function as a nested function and when to go with this approach as used in the solution ?

[@sf-spark129]

I think the interviewers will always be patient enough for you to try with/without helper function. I sometimes use helper() function even though the problem can be solved without it. So, just try with it and without it. In this particular case, it makes more sense to me to nest the helper() function inside the main() function because the code is written in a logically sequential way. Base Case defined -> Same Tree check -> LeftNode, RightNode Recursive call -> return final result Code below: def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: if not subRoot: return True if not root: return False def isSametree(t1, t2) -> bool: if not t1 and not t2: return True if not t1 or not t2: return False leftNode = isSametree(t1.left, t2.left) rightNode = isSametree(t1.right, t2.right) return leftNode and rightNode and t1.val == t2.val if isSametree(root, subRoot): return True leftNode = self.isSubtree(root.left, subRoot) rightNode = self.isSubTree(root.right, subRoot) return leftNode or rightNode

[@dollyvishwakarma2]

@@sf-spark129 True, even I fount it intuitive to use a nested helper here, so I just wanted to check if there is any standard that is recommended. Thank you for you elaborate response :)

[@torin755]

Would it be more efficient (but longer code) overall to first DFS your way down to the bottom, then work bottom up ONLY comparing the heights of the subtree to the currently traversed subtree, and then ONLY if they match do you perform the equal operation? In this way surely you can avoid checking sameTree for EVERY node and replace it with a single height operation for 1 subtree compared to an integer.

[@andriidanylov9453]

Appreciate. Got it

[@hwang1607]

thank you

[@mehmetnadi8930]

great solution! thanks.

[@Wolverine30303x]

What is the space complexity of double, nested recursive call?

[@ZSonnenblick]

Nice solution but I swear theres something with the python community that loves making code as short and unreadable as possible which is a horrible habit. If you're going to abbreviate tree and subtree why not at least give Tree the t and Subtree the s...seems logical. Replacing tree with s and subtree with t is just a truly strange thing to do Having your code a few more characters long if it severely improves readability is actually a good thing anyways nice solution.

[@davidfranke6178]

They may have updated this, but t has to be at least size 1, so no need for if not t: return True

[@andreytamelo1183]

Thanks!

[@NeetCode]

Thank you so much!

[@draugno7]

This is my optimization from Same Tree problem, resulting in Beats 90% in mem. complexity: public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) return true; if (p == null || q == null) return false; if (p.val != q.val) return false; //optimization: if (isSameTree(p.left, q.left) == false) return false; if (isSameTree(p.right, q.right) == false) return false; return true; // //return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); // this is less efficient } my solution also includes this optimization - don't start recursive fn if the vals are not the same: public boolean isSubtree(TreeNode root, TreeNode subRoot) { if (subRoot == null) return true; if (root == null) return false; if (root.val == subRoot.val) { //optimization, we don't start recursion right away if the vals are not the same! if (isSameTree(root, subRoot)) return true; } return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot); }

[@pabloarkadiuszkalemba7415]

Couldn't we improve the performance by first checking the height of the subtree, and then only checking the subtrees that match with that height ? The complexity I think would be n + 2^(log(m)) * m. Because we only check the comparison in the same height, and the same height nodes are 2 ^ m_height == 2 ^ log(m) We could lose performance if subtree > node. But we can fix that returning false in that case in the precondition.

[@stefan.musarra]

I also solved it by first storing the height of every node in the root tree in a cache, so one recursive call to height on the root stores the height at every node. Then I used an iterative DFS on the root to compare heights, and did not continue traversal in subtrees with a lesser height.

[@whonayem01]

Thanks.

[@gamester2495]

is there way to do better than O(m*n), i did same solution in java and is 1ms can i do 0ms?

[@midasredblade236]

could you please explain the tree hash solution?

[@sylviawong6790]

Thank you so much for your effort!!! It helps me a lot in solving Leetcode questions.

[@sulthanmogal9692]

is this optimal ?can we do it in O(T) and space O(T)

[@rohanmahajan6333]

I really don't understand the intuition of knowing to put the 'return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)' within isSubtree. I was able to come up with the intuition of this line, but I was trying it within the sameTree function and i am passing 162/182. Can anyone explain how you know to implement this in the outer function?

[@CameronSantiago-w6i]

Can’t this be done in O(s+t) with a hashmap?

[@mangalegends]

I was able to solve this on my own (well, more like stumble through it) but your code is a lot cleaner than mine lol

[@eduardosanzb]

Would it make sense to do a binary search to find in the root tree all the node that satisfy: "root.Val == subRoot.Val" and from there execute isSameTree? If the binary tree is ordered then it would make sense for speed reasons no?

[@austin4855]

they aren't ordered, as these are not specified to be binary search trees

[@namanvohra8262]

I was able to solve SameTrer but not this, was thinking of post order traversal lol

[@hyungminkim6664]

What is the space complexity?

[@madhurjajoo9404]

Nice work being done on this channel bro!! You helping all of us a lot keep doing it! ps: waiting for java code xd

[@msm1723]

Thank you for your great work!!!

[@theone.591]

Is Space Complexity O(s+t) here? since the call stack could hold at max height of s + height of t function calls?

[@EE12345]

I was wondering the same thing, I also think it's S+T

[@EE12345]

it is

[@madhavaraov3011]

It technically shouldn't work because we have the if subtree != null then return true. this isn't the right case. I took of this line and my code works

[@combatLaCarie]

I believe that there is duplicate work here. We should check to see if the trees are the same after traversing down to the leafs. The moment you find one true the rest of the way up will be true.

[@eraivansaran5836]

Keep on rocking

[@ahmedamr1124]

in the constraints they made both subtree and tree can't be NULL

[@avipatel1534]

Damnit I came here looking for the hash function solution. I codede the brute force earlier today welp rip

[@sourabhxp92]

Bro forgot to read the problem Constraints: The number of nodes in the root tree is in the range [1, 2000]. The number of nodes in the subRoot tree is in the range [1, 1000]. so its guaranteed to have atleast 1 node in both the trees or maybe they updated it after this video

[@bishakhneogi6504]

what is the tc of this function?

[@rajivsarkar277]

nice one

[@midasredblade236]

yes , of course you would explain the O(m*n) solution 😐

[@sanooosai]

helpful

[@algosavage7057]

Dude, u'r best. time passes and I still find ur videos very helpfull. Thanks for great work. Maybe one day we will meet in google :)

[@EranM]

I was thinking of, know the depth of the subtree, d, and look only in the depth of the big tree - d. So if you have a size 1000000 and subtree of size 10, you won't run so many wasted times, and only look for the appropriate depth

[@millenialmusings8451]

I don't think this is an easy problem. It's medium

[@slizverg23]

Problem’s description says that there will be at least 1 node in each tree, so there is no need to check edge cases with empty trees. Anyway, huge thanks for your great work:)

[@jay5929]

no you still have to check, because the recursive calls can have null as parameter. you can test it and see

[@ayoubalem865]

I hope you can solve this problem : you are given an integer n , count the number of beautiful strings with the length of n that we can have. beautiful string is string of only vowels : "a", "e", "i", "o", and "u", also the sort of the vowels should be respected. Exemple : "aae" is beatiful string with length of 3. "eeai" is not because we have "e" before "a" , it does not respect the sort of the vowels. "azio" is not because it contains "z" wich is not a vowel i'm looking for a solution more efficient than this one that i ended up with: def solve(n): vow = ["a", "e", "i", "o", "u"] def bck(i, n, tot): if i >= len(vow): return 1 if n == 0 else 0 if n == 0: return 1 if tot else 0 res1 = bck(i, n - 1, tot + 1) res2 = bck(i + 1, n, tot) return res1 + res2 return bck(0, n, 0)

[@solodolo42]

Thank you bro. But how on earth is this an easy problem? lmao am I missing something?

[@jaskeeratsingh5772]

here is the simplified code class nodes: def __init__(self,data) -> None: self.data = data self.right = None self.left = None class main: def isub(self,s:nodes,t:nodes): if t.right or t.left == s : return True else: return False node1 = nodes(3) node2 = nodes(4) node3 = nodes(2) node1.right = node2.data node1.left = node3.data print(main().isub(node1,node3))

[@kbollins]

am I the only one who thinks this shouldn't be an easy problem?

[@rideraff]

Can anyone tell me how the complexity is M*N and not M+N ?

[@ulivego9779]

Because you use the isSame() function on every node while traversing the Root Tree (N) as long as none of the nodes are null, and the isSame() function traverses the subRoot Tree (M). So that is why it is N*M, since we are traversing M nodes for each node in the main tree which has N nodes. Don't know if the explanation will help since I'm not very good at explaining.

[@adityachache]

You are calling the sametree function for each node of the 's' And the sametree function traverses all the nodes of the tree 't' That's why S*T

[@jay-rathod-01]

hey like Indian youtubers can you also make a frequently asked questions spread sheet that covers almost all the ds and algorithm paradigm