Subtree of Another Tree - Leetcode 572 - Python

0:00 - Read the problem
1:40 - Drawing Explanation
6:35 - Edge Cases
8:29 - Coding Explanation

leetcode 572

#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[vert_sr]

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

[recneps]

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

[shubhamthanki]

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.

[johnlocke]

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

[tb]

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

[symbol]

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

[dhruvkhurana]

Thank you man - you're awesome for these videos

[milesba]

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): #optimization
return True
#otherwise check the if it;s a subtree of left subtree or if it's a subtree of right subtree
else:
return ( self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot) )

[theornament]

Great explanation as always! Just a quick note— in this particular problem, the subroot will always have at least one node, so there's no need to check if it's null.

Additionally, instead of placing an if (sameTree(...)) condition at the start, we can simplify it by directly returning the expression. In Java, since logical OR (||) uses short-circuit evaluation, if the first condition is true, the remaining conditions won't be evaluated, as the result is already determined. Python uses short-circuit evaluation too.

So, we can simply write:
return sameTree(root, subroot) || isSubTree(root.left, subroot) || isSubTree(root.right, subroot);

[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

[hugovinhal]

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

[Vishal-]

I did solve SameTree first and it did help. Yes, you are a sort of hero, Leetcode Hero

[PippyPappyPatterson]

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

[adityaprasad]

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.

[kakakashi_]

For better readability, using same structure used in other neetcode tree questions:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def func_traverse(p, q):
if not p and not q:
return True
if not p or not q or p.val != q.val:
return False
return func_traverse(p.left, q.left) and func_traverse(p.right, q.right)

if not root:
return False

if func_traverse(root, subRoot):
return True

return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

[BedroomPianist]

The optimized solutions for this problem are insane

[mengdizheng]

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 .

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

[andrewberumen]

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

[ThethProgrammer]

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<TreeNode*> nodes { root };
bool subTree { false };

while (!nodes.empty())
{
TreeNode* currNode { nodes.front() };
nodes.pop_front();

if (currNode->left != nullptr)
{

}

if (currNode->right != nullptr)
{

}

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);
}
};