Subtree of Another Tree Problem

Problem

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.

Examples

Example 1:

Input:
root = [3,4,5,1,2], subRoot = [4,1,2]
Output:
 true

Example 2:

Input:
root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output:
 false

Solution

Lets denote tree with root as p and tree with subRoot as q.

Method 1 - Using Inorder and Postorder Traversal

Algorithm

• Perform inorder traversal of tree p and store it as string inorderP.
• Perform inorder traversal of tree q and store it as string inorderQ.
• Perform postorder traversal of tree p and store it as string postorderP.
• Perform postorder traversal of tree q and store it as string postorderQ.
• Tree q is a subtree of tree p if:
  • inorderP contains inorderQ (matches the inorder sequence)
  • postorderP contains postorderQ (matches the postorder structure within the identified sequence)

Example

Lets look at example 1: Lets look at inorder:

• inorderP = 1 4 2 3 5
• inorderQ = 1 4 2
• inorderP.contains(inorderQ) is true

Now, lets look at postorder:

• postorderP = 1 2 4 5 3
• postorderQ = 1 2 4
• postorderP.contains(postorderQ) is true

Code

Java

public boolean checkSubtree(Node rootA, Node rootB) {
	String inOrderA = inOrder(rootA, "");
	String inOrderB = inOrder(rootB, "");
	String postOrderA = postOrder(rootA).toString();
	String postOrderB = postOrder(rootB).toString();
	return (inOrderA.toLowerCase().contains(inOrderB.toLowerCase()) && postOrderA.toLowerCase().contains(postOrderB.toLowerCase()));
}

Complexity

• ⏰ Time complexity: O(|p|+|q|). Generating inorder and postorder traversal take O(p) and O(q), but contains may take O(p) assuming KMP algorithm. (#TODO link KMP algorithm). If we use brute forcecontains, then, it will take O(pq).
• 🧺 Space complexity: O(|p|+|q|)

Method 2 - Using Same Tree

We have already seen - Same Tree Problem. Even though method 1 is faster asymptotically (if we use KMP), still that is not that clean.

See the example 2, leaf node in subRoot are not same as root, even though tree matches. So, subtrees have to be same after a somepoint.

Code:

// is q subtree of p
public boolean isSubtree(TreeNode p, TreeNode q) {
	// null tree is always subtree
	if (q == null) {
		return true;
	}
	// we have already checked q, order of if's matter here
	if(p == null) {
		return false;
	}
	
	if (isSameTree(p, q)) {
		return true;
	}
	
	return isSubtree(p.left, q) || isSubtree(p.right, q);
}

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
        return true;
    }
    if (p == null || q == null) {
        return false;
    }

    return p.val == q.val &&
        isSameTree(p.left, q.left) &&
        isSameTree(p.right, q.right);
}

Complexity

• ⏰ Time complexity: O(p + q)
• 🧺 Space complexity: O(NNNXXX)