Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.
Constraints
Approach
Links
GeeksforGeeks
ProgramCreek
YouTube
Examples
Input:
s = [3, 4, 5, 1, 2]
t = [4, 1, 2]
Output: true
Input:
s = [3, 4, 5, 1, 2, null, null, null, null, 0]
t = [4, 1, 2]
Output: false
Solutions
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
/**
* Time complexity : O(m^2 + n^2 + m*n). A total of n nodes of the tree s and m
* nodes of tree t are traversed. Assuming string concatenation takes O(k)
* time for strings of length k and indexOf takes O(m*n).
* Space complexity : O(max(m,n)). The depth of the recursion tree can go
* upto n for tree t and m for tree s in worst case.
*/
public class Solution {
HashSet < String > trees = new HashSet < > ();
public boolean isSubtree(TreeNode s, TreeNode t) {
String tree1 = preorder(s, true);
String tree2 = preorder(t, true);
return tree1.indexOf(tree2) >= 0;
}
public String preorder(TreeNode t, boolean left) {
if (t == null) {
if (left)
return "lnull";
else
return "rnull";
}
return "#"+ t.val + " " + preorder(t.left, true) + " " +
preorder(t.right, false);
}
}
/**
* Time complexity : O(m*n). In worst case(skewed tree) traverse function
* takes O(m*n) time.
* Space complexity : O(n). The depth of the recursion tree can go upto n.
* n refers to the number of nodes in s.
*/
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if(s == null) {
return false;
}
return isSameTree(s, t) || isSubtree(s.left, t) ||
isSubtree(s.right, t);
}
private boolean isSameTree(TreeNode n1, TreeNode n2) {
if(n1 == null && n2 == null) {
return true;
}
if(n1 == null || n2 == null) {
return false;
}
return n1.val == n2.val && isSameTree(n1.left, n2.left) &&
isSameTree(n1.right, n2.right);
}
}
