572. Subtree of Another Tree

* This shit is not an easy problem.
* I realized that it is healthy to add the
return False
statement at the end of the sameTree function because technically my function returns None when the given trees are not the same.
Luckily for me, the check
bool(None) == False, so the code ran without an issue. But adding the statement makes the code more explicit.

Subtree of Another Tree (Easy)
Given two binary trees root and subRoot, return true if there exists a node in root such that the subtree starting from that node is exactly the same as subRoot.

The key idea in this solution is to use two recursive functions. The first function, isSubtree, goes through every node in the main tree and treats each node as a possible starting point. The second function, sameTree, checks whether two trees are exactly identical by comparing their root values and then recursively comparing their left and right children. If the trees match at the current node, we return True. Otherwise, we continue searching in the left or right subtree of root.

Time Complexity: O(m * n)
m = number of nodes in root
n = number of nodes in subRoot
In the worst case, we may try matching subRoot at many nodes in root, and each match attempt can take up to O(n).

Space Complexity: O(h)
due to the recursion stack, where h is the height of the tree
worst case O(m) for a skewed tree

Видео 572. Subtree of Another Tree канала JunCodes