{"post":"

Problem

Given two binary trees with their head nodes root and sub. We need to find that sub is the subtree of root.

Approach

In this problem, we will need to check identical trees.

If sub is NULL then the tree is a subtree of root.
If the subtree is not NULL and the root is NULL then it's not the subtree.
Then we'll check the data of both the nodes and if the data is equal then we will check if the tree is identical or not.
The above steps recursively perform on every node.

#include<bits/stdc++.h>\nusing namespace std;\nstruct Node{\nint data;\nNode* left;\nNode* right;\nNode(int data){\nthis->data = data;\nleft = right = NULL;\n}\n};
\nbool isIdentical(Node *root1, Node *root2){\nif(root1 == NULL && root2 == NULL) return true;
\nif((root1 && !root2) || (!root1 && root2)) return false;\n\nif(root1-&gt;data != root2-&gt;data) return false;\n\nreturn isIdentical(root1-&gt;left, root2-&gt;left) && isIdentical(root1-&gt;right, root2-&gt;right);\n
\n}
\nbool isSubTree(Node* root, Node* sub) {\nif(sub == NULL) return 1;\nif(sub && !root) return 0;
\nif(root-&gt;data == sub-&gt;data){\n    bool res =  isIdentical(root, sub);\n    if(res) return true;\n}\n
\nreturn isSubTree(root->left, sub) ||  isSubTree(root->right, sub);\n}
\nint main() {\n/*\n1\n/    
\n2      3\n/   \\   /  
\n4     5 6    7\n/\nstruct Node root = new Node(1);\nroot->left = new Node(2);\nroot->left->left = new Node(4);\nroot->left->right = new Node(5);\nroot->right = new Node(3);\nroot->right->left = new Node(6);\nroot->right->right = new Node(7);\ncout<<isSubTree(root, root);
\nreturn 0;\n
\n}

TC- O(MN) // where M and N are the number of nodes in given tree

\n","title":"Check for subtree in a Binary Tree","authorDetails":{"name":"studymite","slug":"admin"},"description":"We will find that the given tree is subtree of a binary tree using diffrent approaches.","slug":"check-for-subtree-in-a-binary-tree/","articleId":"636a83417bb1ce5072622afd","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}