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.
Subtree of Another Tree problem
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.
Here are some examples which show which are subtree and which are not:
Recursive Approach
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.
Let’s find out how to do it step-by-step:
- You have to traverse each node of tree A.
- Check if any of the nodes of trees A and B are null and return false.
- If both the nodes are null return true.
- 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.
- If not check for left and right subtree.
- Repeat the same process
Let’s examine the code for the above process.
C++ Code
Here is the C++ program to check if a binary tree is a subtree of another tree:
#include<bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x){
val = x;
left = NULL;
right = NULL;
}
};
bool isSame(TreeNode* root, TreeNode* subRoot){
if(root==NULL && subRoot==NULL) return true;
if(root==NULL || subRoot==NULL) return false;
if(root->val == subRoot->val) return isSame(root->left, subRoot->left) && isSame(root->right,subRoot->right);
return false;
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(root==NULL && subRoot==NULL) return true;
if(root==NULL || subRoot==NULL) return false;
if(root->val == subRoot->val) {
if(isSame(root, subRoot)) return true;
}
if(isSubtree(root->left,subRoot)) return true;
if(isSubtree(root->right,subRoot)) return true;
return false;
}
int main(){
TreeNode* root = new TreeNode(5);
root->left = new TreeNode(2);
root->right = new TreeNode(6);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(4);
root->left->right->left = new TreeNode(3);
TreeNode* subRoot = new TreeNode(2);
subRoot->left = new TreeNode(1);
subRoot->right = new TreeNode(4);
subRoot->right->left = new TreeNode(3);
bool ans = isSubtree(root, subRoot);
cout<<"Is subRoot is a subtree of Root: ";
(ans)? cout<<"True": cout<<"False";
return 0;
}Java Code
Here is the Java program for the recursive approach:
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
left = null;
right = null;
}
}
class SubtreeCheck {
static boolean isSame(TreeNode root, TreeNode subRoot) {
if (root == null && subRoot == null) return true;
if (root == null || subRoot == null) return false;
return root.val == subRoot.val && isSame(root.left, subRoot.left) && isSame(root.right, subRoot.right);
}
static boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null && subRoot == null) return true;
if (root == null || subRoot == null) return false;
if (root.val == subRoot.val && isSame(root, subRoot)) return true;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
public static void main(String[] args) {
TreeNode root = new TreeNode(5);
root.left = new TreeNode(2);
root.right = new TreeNode(6);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(4);
root.left.right.left = new TreeNode(3);
TreeNode subRoot = new TreeNode(2);
subRoot.left = new TreeNode(1);
subRoot.right = new TreeNode(4);
subRoot.right.left = new TreeNode(3);
boolean ans = isSubtree(root, subRoot);
System.out.print("Is subRoot is a subtree of Root: ");
System.out.println(ans ? "True" : "False");
}
}Python Code
Here is the Python solution:
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def is_same(root, sub_root):
if not root and not sub_root:
return True
if not root or not sub_root:
return False
return root.val == sub_root.val and is_same(root.left, sub_root.left) and is_same(root.right, sub_root.right)
def is_subtree(root, sub_root):
if not root and not sub_root:
return True
if not root or not sub_root:
return False
if root.val == sub_root.val and is_same(root, sub_root):
return True
return is_subtree(root.left, sub_root) or is_subtree(root.right, sub_root)
if __name__ == "__main__":
root = TreeNode(5)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(3)
sub_root = TreeNode(2)
sub_root.left = TreeNode(1)
sub_root.right = TreeNode(4)
sub_root.right.left = TreeNode(3)
ans = is_subtree(root, sub_root)
print("Is subRoot is a subtree of Root:", ans)Output:
Is subRoot is a subtree of Root: TrueThe 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.
Conclusion
In this article, we solved ‘Subtree of Another Tree’ problem from leetcode. We saw how we can recursively approach this problem. In this article, we used classes. If you don’t know about classes try to learn them first.
