GFG POTD: Check if subtree | Binary-Tree (Java) | Day 08

Welcome to today's explanation of the GFG POTD (Problem of the Day)! In this video, I break down the strategies, ideas, and core concepts you need to solve the "Check if subtree" problem. Understanding tree traversals and subtree matching will boost your overall problem-solving skills and help you build the solid foundation needed to tackle more complex graph and tree questions next time. If you found this video helpful, please show your gratitude by liking the video, and don't forget to subscribe to the channel for more daily coding content. Happy coding! Problem Name: Check if subtree Difficulty: Medium Platform: GeeksforGeeks Question: Check if subtree The Approach (Recursive Tree Traversal & Matching) Divide the Problem: The most elegant way to solve this is to break it down into two distinct tasks: traversing the main tree (Tree T) to find a potential match, and checking if two subtrees are perfectly identical. The "Identical" Helper Function: Create a helper method (e.g., isIdentical) that takes two nodes. It checks if both are null (true), if only one is null (false), and if their data matches. If the data matches, it recursively checks if their left and right subtrees are also identical. Understand the Base Cases for the Main Function: If the subtree S is null, it's technically a subtree of any tree (return true). If the main tree T is null but S is not, S cannot be a subtree (return false). Check the Current Node: For the current node in Tree T, use your helper function to check if the tree starting at this node is identical to Tree S. If it is, return true! Traverse Left and Right: If the current nodes don't form identical trees, don't give up. Recursively call your isSubTree function on the left child of T and the right child of T. If S is a subtree of either the left or the right branch, return true. Complexity : Time Complexity: $O(N \times M)$ where $N$ is the total number of nodes in tree T and $M$ is the total number of nodes in tree S. In the worst-case scenario (like a tree where all nodes have the same value), we might trigger the isIdentical check at every single node of T, which takes $O(M)$ time for each check. Space Complexity: $O(H)$ where $H$ is the height of the main tree T. This is the auxiliary space required for the recursive call stack. In the worst-case scenario (a highly skewed tree), the height equals $N$, making the space complexity $O(N)$. For a balanced tree, it would be closer to $O(\log N)$. Solution Code: https://github.com/Arnab-Pachal1234/GFG-POTD-SOLUTION #gfg #dsa #binarytree #recursion #coding #problemoftheday #java #mediumquestion #leetcode #competitiveprogramming #datastructures #trees