LeetCode Easy(medium-ish): Subtree of Another Tree

Hello Peeps,

We're getting back in touch with problem solving after a long-long time. I was _really really_ busy with family functions in this break.

Yesterday, I solved this LeetCode problem Subtree of Another Tree categorised as easy on LeetCode. I would say medium would have been a more appropriate categorisation of this recursively solvable problem.

Problem link: https://leetcode.com/problems/subtree-of-another-tree/

Solution Approach: Recursion

Time Complexity: O(n) where n is the number of nodes in the tree s.

Space Complexity: O(h) where h is the height of the tree s.

Solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        
        //Main logic
        boolean matchFound = false;
        
        //Base condition
        if (s == null && t == null)
            return true;

        if ((s!=null && t==null) || (s==null && t!=null))
            return false;

        if (s.val == t.val)
            matchFound = matches (s, t);

        if (!matchFound) {
            matchFound = isSubtree(s.left, t);
        }
        if (!matchFound) {
            matchFound = isSubtree(s.right, t);
        }

        return matchFound;
    }
    
    private boolean matches (TreeNode s, TreeNode t) {
        if (s==null && t==null)
            return true;
        if ((s!=null && t==null) || (s==null && t!=null))
            return false;
        if (s.val != t.val)
            return false;
        return matches(s.left, t.left) && matches(s.right, t.right);
    }
}

That's all for now!

Happy Coding!!