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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s