[Geeks for Geeks] Check if subtree

Check if subtree

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
class Solution
{
bool helper(Node* a, Node* b) {
if(!a and !b) return true;
if(!a or !b) return false;
if(a->data != b->data) return false;
return helper(a->left, b->left) and helper(a->right, b->right);
}
public:
//Function to check if S is a subtree of tree T.
bool isSubTree(Node* T, Node* S)
{
if(!T) return false;
if(helper(T, S)) return true;
return isSubTree(T->left, S) or isSubTree(T->right, S);
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/20/PS/GeeksforGeeks/check-if-subtree/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.