algoadvance

Leetcode 572. Subtree of Another Tree

Problem Statement:

Given the roots of two binary trees root and subRoot, determine if there is a subtree of root with the same structure and node values of subRoot. 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.

Example:

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

Clarifying Questions:

1. Can both root and subRoot be null?
   • Yes, if both are null, return true.
2. If subRoot is null but root is not, what should the output be?
   • If subRoot is null, it should always return true regardless of root.
3. If root is null but subRoot is not, what should the output be?
   • If root is null but subRoot is not, it should return false.

Strategy:

1. Equality Function: Define a helper function isSameTree to check if two trees are identical.
2. Traversal and Subtree Check:
   • Traverse through each node in the main tree (root).
   • For each node in root, check if the subtree starting at that node is equal to subRoot using the isSameTree function.
   • Return true if any subtree matches, otherwise return false.

Code:

// TreeNode class definition
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

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

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

Time Complexity:

• isSameTree Function:
  • To compare two subtrees takes (O(m)) time where (m) is the number of nodes in the subtree.
• isSubtree Function:
  • This function essentially visits every node in root and calls isSameTree which takes (O(m)) time for each node.
  • Thus, the total time complexity is (O(n * m)) where (n) is the number of nodes in root and (m) is the number of nodes in subRoot.

The given solution efficiently checks subtrees using recursive techniques, ensuring each possible subtree is validated against subRoot.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?