This approach involves using a recursive function to traverse the root tree and checking for a matching subtree starting from every node. A helper function can be used to check if trees rooted at specific nodes are identical.
Time Complexity: O(N*M), where N is the number of nodes in the root tree and M is the number of nodes in subRoot tree.
Space Complexity: O(min(N, M)), depending on the tree height during recursion.
1var isSubtree = function(root, subRoot) {
2 if (!root) return false;
3 if (isIdentical(root, subRoot)) return true;
4 return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
5};
6
7var isIdentical = function(s, t) {
8 if (!s && !t) return true;
9 if (!s || !t) return false;
10 return s.val === t.val && isIdentical(s.left, t.left) && isIdentical(s.right, t.right);
11};The JavaScript solution is similar in logic to other solutions, employing two functions: isSubtree and isIdentical. It checks recursively whether the trees rooted at two nodes are the same.
Another approach to solving this problem is by converting the trees into their preorder traversal strings with marker symbols for nulls, and then checking if the subRoot string is a substring of the root string.
Time Complexity: O(N + M + N*M), where N and M are the sizes of the trees.
Space Complexity: O(N + M), for the preorder traversal strings.
1class Solution:
2 def isSubtree(self, root, subRoot):
3 return self.preorder(root).find(self.preorder(subRoot)) != -1
4
5 def preorder(self, node):
6 if not node:
7 return "null "
8 return str(node.val) + " " + self.preorder(node.left) + self.preorder(node.right)The Python solution uses preorder traversal to obtain a string representation of both trees and checks the inclusion of subRoot's string representation within root's string.