Subtree of Another Tree

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree that consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Example:

Input:  s= {3,4,5,1,2}, t={4,1,2}
Output: true

Approach

Java

public class SubtreeAnotherTree {
    public static void main(String[] args) {
        TreeNode s = new TreeNode(3);
        s.left = new TreeNode(4);
        s.right = new TreeNode(5);
        s.left.left = new TreeNode(1);
        s.left.right = new TreeNode(2);

        TreeNode t = new TreeNode(4);
        t.left = new TreeNode(1);
        t.right = new TreeNode(2);

        System.out.println(isSubtree(s, t));
    }

    static boolean isSubtree(TreeNode s, TreeNode t) {
        if (t == null)
            return true;
        if (s == null)
            return false;
        if (isIdentical(s, t))
            return true;
        // call for left subtree and right subtree
        return isSubtree(s.left, t) || isSubtree(s.right, t);
    }

    static boolean isIdentical(TreeNode s, TreeNode t) {
        if (s == null && t == null)
            return true;
        if (s == null || t == null)
            return false;
        return (s.val == t.val && isIdentical(s.left, t.left) 
                    && isIdentical(s.right, t.right));
    }

}

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;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode
{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

bool isIdentical(TreeNode *s, TreeNode *t)
{
    if (s == NULL && t == NULL)
        return true;
    if (s == NULL || t == NULL)
        return false;
    return (s->data == t->data && isIdentical(s->left, t->left) 
            && isIdentical(s->right, t->right));
}
bool isSubtree(TreeNode *s, TreeNode *t)
{
    if (t == NULL)
        return true;
    if (s == NULL)
        return false;
    if (isIdentical(s, t))
        return true;
    //call for left subtree and right subtree
    return isSubtree(s->left, t) || isSubtree(s->right, t);
}

int main()
{

    TreeNode *s = new TreeNode(3);
    s->left = new TreeNode(4);
    s->right = new TreeNode(5);
    s->left->left = new TreeNode(1);
    s->left->right = new TreeNode(2);

    TreeNode *t = new TreeNode(4);
    t->left = new TreeNode(1);
    t->right = new TreeNode(2);

    if (isSubtree(s, t))
        cout << "true";
    else
        cout << "false";

    return 0;
}