{"id":1955,"date":"2024-03-13T18:00:00","date_gmt":"2024-03-13T18:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1955"},"modified":"2024-03-14T10:41:35","modified_gmt":"2024-03-14T10:41:35","slug":"subtree-of-another-tree","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/subtree-of-another-tree\/","title":{"rendered":"Check If Binary Tree is Subtree of Another Tree (with code)"},"content":{"rendered":"\n

Trees are an important data structure but are difficult to master. There are many questions asked in interviews based on the tree, but here we will solve the ‘Subtree of Another Tree’ problem with solutions in C++, Java, and Python. <\/p>\n\n\n\n

Subtree of Another Tree problem<\/strong><\/h2>\n\n\n\n

In the Subtree of Another Tree problem, we are given the roots of two binary trees A and B. We have to find if there is any subtree of A having the same structure and values as subtree B.\u00a0<\/p>\n\n\n\n

Here are some examples which show which are subtree and which are not:<\/p>\n\n\n\n

\"Example<\/figure>\n\n\n\n

Recursive Approach<\/strong><\/h2>\n\n\n\n

To find whether the given subtree is a subtree of A or not. We have to recursively traverse tree A and check at each node whether this subtree is the same as subtree B. If it is return true otherwise traverse the left and right node. If there is no such tree you have to return false.<\/p>\n\n\n\n

Let\u2019s find out how to do it step-by-step:<\/p>\n\n\n\n

    \n
  1. You have to traverse each node of tree A.<\/li>\n\n\n\n
  2. Check if any of the nodes of trees A and B are null and return false.<\/li>\n\n\n\n
  3. If both the nodes are null return true.<\/li>\n\n\n\n
  4. Now check if the value is the same for both nodes or not. If it is check if both the trees, tree B and subtree of A are the same if it is return true.<\/li>\n\n\n\n
  5. If not check for left and right subtree.<\/li>\n\n\n\n
  6. Repeat the same process<\/li>\n<\/ol>\n\n\n\n

    Let\u2019s examine the code for the above process.<\/p>\n\n\n\n

    C++ Code<\/strong><\/h3>\n\n\n\n

    Here is the C++ program to check if a binary tree is a subtree of another tree:<\/p>\n\n\n\n

    #include<bits\/stdc++.h>\nusing namespace std;\n\n    class TreeNode{\n        public:\n        int val;\n        TreeNode* left;\n        TreeNode* right;\n\n        TreeNode(int x){\n            val = x;\n            left = NULL;\n            right = NULL;\n        }  \n    };\n\n    bool isSame(TreeNode* root, TreeNode* subRoot){\n        if(root==NULL && subRoot==NULL) return true;\n        if(root==NULL || subRoot==NULL) return false;\n        if(root->val == subRoot->val) return isSame(root->left, subRoot->left) && isSame(root->right,subRoot->right);\n        return false;\n    }\n    bool isSubtree(TreeNode* root, TreeNode* subRoot) {\n        if(root==NULL && subRoot==NULL) return true;\n        if(root==NULL || subRoot==NULL) return false;\n        if(root->val == subRoot->val) {\n            \n            if(isSame(root, subRoot)) return true;\n        }\n        if(isSubtree(root->left,subRoot)) return true;\n        if(isSubtree(root->right,subRoot)) return true;\n        return false;\n    }\n\n\n    int main(){\n        TreeNode* root = new TreeNode(5);\n        root->left = new TreeNode(2);\n        root->right = new TreeNode(6);\n        root->left->left = new TreeNode(1);\n        root->left->right = new TreeNode(4);\n        root->left->right->left = new TreeNode(3);\n\n        TreeNode* subRoot = new TreeNode(2);\n        subRoot->left = new TreeNode(1);\n        subRoot->right = new TreeNode(4);\n        subRoot->right->left = new TreeNode(3);\n\n        bool ans = isSubtree(root, subRoot);\n        cout<<"Is subRoot is a subtree of Root: ";\n        (ans)? cout<<"True": cout<<"False";\n        return 0;\n    }<\/pre><\/div>\n\n\n\n
    Java Code<\/strong><\/h3>\n\n\n\n
    Here is the Java program for the recursive approach:<\/p>\n\n\n\n
    class TreeNode {\n    int val;\n    TreeNode left;\n    TreeNode right;\n\n    TreeNode(int x) {\n        val = x;\n        left = null;\n        right = null;\n    }\n}\n\nclass SubtreeCheck {\n    static boolean isSame(TreeNode root, TreeNode subRoot) {\n        if (root == null && subRoot == null) return true;\n        if (root == null || subRoot == null) return false;\n        return root.val == subRoot.val && isSame(root.left, subRoot.left) && isSame(root.right, subRoot.right);\n    }\n\n    static boolean isSubtree(TreeNode root, TreeNode subRoot) {\n        if (root == null && subRoot == null) return true;\n        if (root == null || subRoot == null) return false;\n        if (root.val == subRoot.val && isSame(root, subRoot)) return true;\n        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);\n    }\n\n    public static void main(String[] args) {\n        TreeNode root = new TreeNode(5);\n        root.left = new TreeNode(2);\n        root.right = new TreeNode(6);\n        root.left.left = new TreeNode(1);\n        root.left.right = new TreeNode(4);\n        root.left.right.left = new TreeNode(3);\n\n        TreeNode subRoot = new TreeNode(2);\n        subRoot.left = new TreeNode(1);\n        subRoot.right = new TreeNode(4);\n        subRoot.right.left = new TreeNode(3);\n\n        boolean ans = isSubtree(root, subRoot);\n        System.out.print("Is subRoot is a subtree of Root: ");\n        System.out.println(ans ? "True" : "False");\n    }\n}<\/pre><\/div>\n\n\n\n
    Python Code<\/strong><\/h3>\n\n\n\n
    Here is the Python solution:<\/p>\n\n\n\n
    class TreeNode:\n    def __init__(self, x):\n        self.val = x\n        self.left = None\n        self.right = None\n\ndef is_same(root, sub_root):\n    if not root and not sub_root:\n        return True\n    if not root or not sub_root:\n        return False\n    return root.val == sub_root.val and is_same(root.left, sub_root.left) and is_same(root.right, sub_root.right)\n\ndef is_subtree(root, sub_root):\n    if not root and not sub_root:\n        return True\n    if not root or not sub_root:\n        return False\n    if root.val == sub_root.val and is_same(root, sub_root):\n        return True\n    return is_subtree(root.left, sub_root) or is_subtree(root.right, sub_root)\n\nif __name__ == "__main__":\n    root = TreeNode(5)\n    root.left = TreeNode(2)\n    root.right = TreeNode(6)\n    root.left.left = TreeNode(1)\n    root.left.right = TreeNode(4)\n    root.left.right.left = TreeNode(3)\n\n    sub_root = TreeNode(2)\n    sub_root.left = TreeNode(1)\n    sub_root.right = TreeNode(4)\n    sub_root.right.left = TreeNode(3)\n\n    ans = is_subtree(root, sub_root)\n    print("Is subRoot is a subtree of Root:", ans)<\/pre><\/div>\n\n\n\n
    Output:<\/strong> <\/p>\n\n\n\n
    Is subRoot is a subtree of Root: True<\/code><\/pre>\n\n\n\n
    The time complexity to check if a binary tree is a subtree of another tree is O(n*m) where n is the number of nodes in a tree and m is several nodes in a subtree. The space complexity is O(1) as we are not using any extra space.\u00a0<\/p>\n\n\n\n
    Conclusion<\/strong><\/h2>\n\n\n\n
    In this article, we solved ‘Subtree of Another Tree’ problem from leetcode<\/a>. We saw how we can recursively approach this problem. In this article, we used classes. If you don\u2019t know about classes<\/a> try to learn them first. <\/p>\n","protected":false},"excerpt":{"rendered":"
    Understand the Subtree of Another Tree problem using the recursive approach, with implementation in C++, Java, and Python.<\/p>\n","protected":false},"author":14,"featured_media":2040,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[105,14,15],"class_list":["post-1955","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-binary-tree","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1955","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=1955"}],"version-history":[{"count":8,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1955\/revisions"}],"predecessor-version":[{"id":2405,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1955\/revisions\/2405"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/2040"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1955"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1955"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1955"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}