# Java Solution, tree traversal

• For each node during pre-order traversal of `s`, use a recursive function `isSame` to validate if sub-tree started with this node is the same with `t`.

``````public class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) return false;
if (isSame(s, t)) return true;
return isSubtree(s.left, t) || isSubtree(s.right, t);
}

private boolean isSame(TreeNode s, TreeNode t) {
if (s == null && t == null) return true;
if (s == null || t == null) return false;

if (s.val != t.val) return false;

return isSame(s.left, t.left) && isSame(s.right, t.right);
}
}
``````

• Same idea. I use iterative way for isSubtree to save one extra method...

``````public boolean isSubtree(TreeNode s, TreeNode t) {
Queue<TreeNode> nodes = new ArrayDeque<>();
nodes.offer(s);
while (!nodes.isEmpty()) {
TreeNode node = nodes.poll();
if (isSameTree(node, t)) {
return true;
}
if (node.left != null) {
nodes.offer(node.left);
}
if (node.right != null) {
nodes.offer(node.right);
}
}
return false;
}

public boolean isSameTree(TreeNode s, TreeNode t) {
if (s == null && t == null) {
return true;
}
if (s == null || t == null) {
return false;
}
if (s.val != t.val) {
return false;
} else {
return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
}
}
``````

• clear and straightforward, nice solution!

• @shawngao I think the isSame() can be modified like this

``````private boolean isSame(TreeNode s, TreeNode t) {
if(s==null||t==null)return s==t;
if (s.val != t.val) return false;
return isSame(s.left, t.left) && isSame(s.right, t.right);
}
}
``````

• @shawngao Maybe there is no need to check `if (s.val == t.val)` in `isSubtree` since it will be checked in your `isSame` at the first attempt.

C++ version:

``````class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
if (isIdentical(s, t))
return true;
return (s->left == nullptr ? false: isSubtree(s->left, t))
|| (s->right == nullptr ? false: isSubtree(s->right, t));
}

// whether two trees are identical (both structure and node values)
bool isIdentical(const TreeNode* s, const TreeNode* t){
if (s == nullptr && t == nullptr)
return true;
if ((s == nullptr && t != nullptr) || (s != nullptr && t == nullptr))
return false;
// both non nullptr
if (s->val != t->val)
return false;
return isIdentical(s->left, t->left) && isIdentical(s->right, t->right);

}
};``````

• @shuhua Yes, you are right. Modified my post, thanks!

• @shawngao

Very clean implementation !

• @shawngao

I have the same idea with you. But I am kind of worried if the solution efficient enough.
Because isSame method takes O(n) time and O(n) space. So the time complexity should be O(n ^ 2).

Is there any more efficient way so it could run in linear time?

• I think the first line of function isSame should be like this:
if(s == t) return true; which means

• A: s==null && t==null
• B: s and t are the same node

• Same idea.

``````public class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (isSameTree(s, t))   return true;
if (s == null)  return false;
return isSubtree(s.left, t) || isSubtree(s.right, t);
}

private boolean isSameTree(TreeNode s, TreeNode t) {
if (s == null && t == null) return true;
if (s == null || t == null) return false;

return s.val == t.val && isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
}
}
``````

• Similar C++ solution

``````class Solution {
public:
bool isSubtree(TreeNode* s, TreeNode* t) {
return isSametree(s, t) || (s != nullptr && (isSubtree(s -> left, t) || isSubtree(s -> right, t)));
}

bool isSametree(TreeNode *s, TreeNode *t) {
if(s == nullptr && t == nullptr)  return true;
if(s == nullptr || t == nullptr)  return false;
return s -> val == t -> val && isSametree(s -> left, t -> left) && isSametree(s -> right, t -> right);
}
};
``````

• what if TreeNode t is null? Since an empty tree is always a subtree, we need to return true.

'''
public boolean isSubtree(TreeNode s, TreeNode t){
if (t == null) return true;// the empty tree is always a subtree
return subTree(s, t);
}

``````public boolean subTree(TreeNode r1, TreeNode r2){
if (r1 == null){
return false; //big tree empty
} else if (matchTree(r1, r2)){
return true;
}
return subTree(r1.left, r2)||subTree(r1.right, r2);

}
public boolean matchTree(TreeNode r1, TreeNode r2){
if (r1 == null && r2 == null) return true;
if (r1 == null || r2 == null) return false;
if (r1.val != r2.val) return false; // data doesn't match
return matchTree(r1.left, r2.left) && matchTree(r1.right, r2.right);
}
``````

'''

• This post is deleted!

• Mine is the same

``````public class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if(s == null && t !=null) return false;
return isSame(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}
public boolean isSame(TreeNode treeA, TreeNode treeB) {
if (treeA == null && treeB == null) {
return true;
}
else if (treeA == null || treeB == null) {
return false;
}
return treeA.val == treeB.val && isSame(treeA.left, treeB.left) && isSame(treeA.right, treeB.right);
}
}

``````

• same:

``````public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) return t == null;
return sameTree(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}

private boolean sameTree(TreeNode s, TreeNode t) {
if (s == null && t == null) return true;
if (s == null || t == null) return false;
return s.val == t.val && sameTree(s.left, t.left) && sameTree(s.right, t.right);
}``````

• @jz34 Looks good.
But why my code is not accepted by OJ?

The only one failed case is [1,2] [2], and expected result is false, my code returns true. But why? what [1,2] stands for?

public class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {

``````    String s1 = Serialize(s);
String s2 = Serialize(t);
return s1.indexOf(s2) > -1;

}

String Serialize(TreeNode root){
if(root == null) return "null";
return root.val + Serialize(root.left) + Serialize(root.right);
}
``````

}

• @Angaojxz
[1,2]: "12nullnullnull"
[2]: "2nullnull"
[2] is inside [1,2] according to your algorithm

• @jz34

Thanks,

Following works

public class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {

``````    String s1 = Serialize(s);
String s2 = Serialize(t);
return s1.indexOf(s2) > -1;

}

String Serialize(TreeNode root){
if(root == null) return "null";
return "#" + root.val + Serialize(root.left) + Serialize(root.right);
}
``````

}

• @shawngao Nice work, buddy! I am with the same idea with @shuhua ( does not need to check if (s.val == t.val) in the first line of isSubtree at first, but it is very interesting that the Java version without the check line cannot pass with the error " java.lang.NullPointerException" pointed to the line return isSubtree(s.left, t) || isSubtree(s.right, t) . However the C++ version @shuhua provided can pass. Wierd, I don't why, is it because if s.left (or s.right) is null then s.left (or s.right) cannot be passed as parameters? Hope anybody can explain, great thanks!

• @JansonLu
The only "linear time" way I can imagine is to put all nodes into a pre/mid/postorder string and compare them, I remember some string compare method is linear time? We know that we need two strings (preorder + midorder for example)to describe a tree, thus the process could be described as below:

``````1. ps = preorder s
2. ms = midorder s
3. pt = preorder t
4. mt = midorder t
5. return (pt is substr of ps) && (mt is substr of ms)
``````

The only problem is that, some substructure of s may have same preorder string with t, while other substructure of t may have same midorder string with t, in this circumstance the algorithm returns true but actually it's false. So I don't think this linear algorithm works for the problem.

NOTE: To construct a faulty test case of this algorithm, you can find a tree u that has same preorder string with t, and another tree v that has same midorder string with t, and use them as the left & right child of any node to contruct s.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.