Given two binary trees with head reference as T and S having at most N nodes. The task is to check if S is present as subtree in T.
A subtree of a tree T1 is a tree T2 consisting of a node in T1 and all of its descendants in T1.
Time : O(n)
Space : O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution { boolhelper(Node* a, Node* b){ if(!a and !b) returntrue; if(!a or !b) returnfalse; if(a->data != b->data) returnfalse; returnhelper(a->left, b->left) andhelper(a->right, b->right); } public: //Function to check if S is a subtree of tree T. boolisSubTree(Node* T, Node* S) { if(!T) returnfalse; if(helper(T, S)) returntrue; returnisSubTree(T->left, S) orisSubTree(T->right, S); } };