Subtree of Another Tree

​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.

Example: Given tree s:

```     3
/ \
4   5
/ \
1   2
```

Given tree t:

```   4
/ \
1   2
```

Return true, because t has the same structure and node values with a subtree of s. We can find the preorder traversal of the given trees s and t, given by, say `Spreorder` and `Tpreorder` respectively(represented in the form of a string). Now, we can check if `Tpreorder` is a substring of `Spreorder`. You can also note that we’ve added a ‘#’ before every considering every value. If this isn’t done, the trees of the form `s:[12]` and `t:[2]` will also give a true result since the preorder string of the `t("2 null null")` will be a substring of the preorder string of `s("12 null null")`. Adding a ‘#’ before the node’s value solves this problem.

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null && t == null) return true;
if (s == null || t == null) return false;
StringBuilder sb1 = new StringBuilder();
StringBuilder sb2 = new StringBuilder();
preOrder(s, sb1);
preOrder(t, sb2);
return sb1.toString().indexOf(sb2.toString()) >= 0;
}

private void preOrder(TreeNode node, StringBuilder builder) {
if (node == null) {
builder.append("null");
return;
}
builder.append("#").append(node.val);
preOrder(node.left, builder);
preOrder(node.right, builder);
}
}
```

Complexity Analysis

• Time complexity : O(m2 + n2 + 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 the worst case.

Categories: Binary Tree