Prerequisites: Binary trees, Binary tree traversal.
Problem: Given two undirected binary trees T1 and T2,check if the second tree T2 exists as a subtree in the first tree T1.
Solution Approach: This problem can be solved using a recursive approach to check if T2 is a subtree of T1. The key function here is sameTree(), which checks whether two trees are identical. The main function findSubtree() then uses this helper function recursively to find if any subtree in T1 is identical to T2.
Time Complexity: The time complexity of this solution is O(m * n), where m is the number of nodes in T1 and n is the number of nodes in T2. This is because, in the worst case, we may have to check every node in T1 against T2.
Space Complexity: The space complexity is O(max(m, n)), where m is the height of T1 and n is the height of T2. The space complexity is determined by the recursive calls on the height of the trees.