Recursion and Trees
A recursion that calls another recursion
One walk to visit every node, another to test each one. Two functions, and the cost multiplies.
Key idea
Separate the walking from the testing
Some questions are of the form: does any node in this tree satisfy some property that is itself about a whole subtree?
Trying to do both jobs in one function produces something confusing. Write two: an outer one that visits every node, and an inner one that answers the property for a single node. The outer one calls the inner one at each stop.
Cost
The cost multiplies
The outer walk visits n nodes. If the inner test is itself a full subtree walk, it costs up to n, so the total is O(n squared) in the worst case.
That is often acceptable and you should say it rather than hide it. For a balanced tree the real total is closer to O(n log n), because the subtree walked at each node shrinks with depth, but the worst case on a degenerate tree is genuinely quadratic.
If a problem's constraints rule that out, the escape is usually to serialize both trees and search for one string inside the other, which is a different technique entirely.
Tip
Stopping early
When the question is does any rather than how many, the outer walk can stop at the first success. Python's or short-circuits, so writing the recursive calls joined by or gives that for free.
The order of the checks then matters for speed but not for correctness: testing the current node before recursing means an early match costs nothing.
Edge cases
What does an empty subtree count as?
For a problem asking whether one tree contains another as a subtree, decide early what happens when the thing being searched for is empty. Conventionally an empty tree is a subtree of anything, including of an empty tree.
Most versions of the problem below promise a non-empty target, which removes the question. Check for the promise rather than assuming, because the two conventions give different answers on the same input.
Predict the output: matching from the wrong place
same_shape checks two trees for an exact match. The pattern here does appear inside the big tree, but not starting at the node being tested. Type the two values it prints, separated by a single space.
Subtree Of Another Tree
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.