Subtree of Another Tree.md

Algorithm

Use Preorder traversal to convert each tree into a String.

Replace each null with an X. This is necessary to distinguish between trees such as

  1         1
 /    vs.    \
2             2

  1
 /     would incorrectly be "12". Now it's "12X"
2

  1
   \   would incorrectly be "12". Now it's "1X2"
    2

Since each TreeNode value is an int, we can safely append a # symbol in front of it to distinguish between the following trees:

  1            12
 /     vs.     /
23            3

  1
 /   would incorrectly be "123X". Now it's "#1#23X"
23

  1
 /   would incorrectly be "123X". Now it's "#1#23X"
23

After converting the 2 trees to 2 Strings, iff String 2 is a substring of String 1, then tree 2 is a subtree of tree 1.

Provided Code

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

Solution

class Solution {
    public boolean isSubtree(TreeNode t1, TreeNode t2) {
        StringBuffer sb1 = new StringBuffer();
        StringBuffer sb2 = new StringBuffer();
        getPreorder(t1, sb1);
        getPreorder(t2, sb2);
        return sb1.indexOf(sb2.toString()) != -1;
    }

    private void getPreorder(TreeNode node, StringBuffer sb) {
        if (node == null) {
            sb.append("X");
            return;
        }
        sb.append("#" + node.val);
        getPreorder(node.left, sb);
        getPreorder(node.right, sb);
    }
}

Time/Space Complexity

• Time Complexity: O(m + n) if .indexOf() uses KMP algorithm.
• Space Complexity: O(m + n)

Java's implementation for .indexOf() for Strings is naively O(n²) since it doesn't use the KMP algorithm! If .indexOf() is this slow for StringBuffer, then use this O(n) implementation of KMP algorithm instead.

Links

• github.com/RodneyShag