Subtree of Another Tree

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.

OR

You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

Examples

Example 1:

graph LR
	subgraph root
        A(3)
        A --- B(4)
        A --- C(5)
        

	subgraph " "
		B --- D(1)
        B --- E(2)
	end
	end

    subgraph subRoot
        D2(4)
        D2 --- A2(1)
        D2 --- B2(2)
    end
    root ~~~ subRoot

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

Example 2:

graph LR
    subgraph root
        C(3)
        C --- D(4)
        C --- E(5)
        D --- A(1)
        D --- B(2)
        B --- F(0)
        B ~~~ N1:::hidden
    end

    subgraph subRoot
        D2(4)
        D2 --- A2(1)
        D2 --- B2(2)
    end
    
    root ~~~ subRoot
    
    classDef hidden display:none

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.

Video explanation

Here is the video explaining this method in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/Wb8MXm2oxt4" frameborder="0" allowfullscreen></iframe></div>

Method 1 - Using Recursive DFS and Same Tree

We have already seen - [Same Tree](same-tree). 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

Java

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

    private boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null || p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Python

// 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(|p|+|q|), where |p| is the number of nodes in tree p and |q| is the number of nodes in tree q.
  • The recursion stack for isSubtree can go as deep as O(|p|) in the worst case.
  • For each call to isSameTree, the recursion stack can go as deep as O(|q|).
  • So, the total space used by the recursion stack is O(|p| + |q|) in the worst case.

Method 2 - Using Tree Serialization with preorder or postorder traversal

Intuition

The recursive approach can be inefficient due to repeated comparisons. A more optimal method is to represent each tree by a unique string. If the subRoot's string is a substring of the root's string, we have a match.

Approach

1. Serialization Strategy: We must convert the tree to a string in a way that is unambiguous.

   • Traversal Order: A pre-order or post-order traversal is required. This is because they keep the root's value at a fixed position relative to its children, ensuring a unique mapping from tree to string. An in-order traversal will not work as it can produce the same string for different tree structures.
   • Separators & Nulls: We must use a separator (e.g., #) to distinguish values (like 1,2 from 12) and a special marker (e.g., n) for null children to perfectly preserve the tree's structure.

2. The Algorithm:

   • Generate the unique string for root using the serialization strategy (e.g., pre-order).
   • Generate the unique string for subRoot using the same strategy.
   • Check if the subRoot string is a substring of the root string. Most languages provide a built-in function for this.

Complexity

• ⏰ Time complexity: O(m + n). Generating the strings takes O(m) and O(n). The substring search is also typically O(m + n).
• 🧺 Space complexity: O(m + n) to store the two generated strings.

Code

Java

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        StringBuilder s1 = new StringBuilder();
        StringBuilder s2 = new StringBuilder();
        
        serialize(root, s1);
        serialize(subRoot, s2);
        
        return s1.toString().contains(s2.toString());
    }
    
    private void serialize(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("#n");
            return;
        }
        
        sb.append("#").append(node.val);
        serialize(node.left, sb);
        serialize(node.right, sb);
    }
}

Python

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        s1 = []
        s2 = []
        
        self.serialize(root, s1)
        self.serialize(subRoot, s2)
        
        s1_str = "".join(s1)
        s2_str = "".join(s2)
        
        return s2_str in s1_str
        
    def serialize(self, node: Optional[TreeNode], s: list[str]):
        if not node:
            s.append("#n")
            return
            
        s.append(f"#{node.val}")
        self.serialize(node.left, s)
        self.serialize(node.right, s)

Method 3 - 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:

graph LR
	subgraph root
        A(3)
        A --- B(4)
        A --- C(5)
        

	subgraph " "
		B --- D(1)
        B --- E(2)
	end
	end

    subgraph SubRoot
        D2(4)
        D2 --- A2(1)
        D2 --- B2(2)
    end

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|)