Solution For Subtree Of Another Tree

The Subtree Of Another Tree problem on LeetCode asks you to determine if a given binary tree is a subtree of another binary tree.

Here is the problem statement:

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 1:

Given the following tree s:

     3
    / \
   4   5
  / \
 1   2

Given the following tree t:

   4
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s.

Example 2:

Given the following tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Given the following tree t:

   4
  / \
 1   2

Return false.

The solution to this problem can be approached using recursion. To check if tree t is a subtree of s, we need to check if tree t is a subtree of both the left and right subtrees of s.

We can define a helper function called isSameTree that checks if two trees are the same. This function can be called recursively to check if the subtree of s at each node is the same as t.

Here is the solution in Python:

“`
class Solution:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
if not s:
return False
if self.isSameTree(s, t):
return True
return self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

def isSameTree(self, s: TreeNode, t: TreeNode) -> bool:
    if not s and not t:
        return True
    if not s or not t:
        return False
    if s.val != t.val:
        return False
    return self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)

“`

In the isSubtree function, we first check if s is empty. If s is empty, then t cannot be a subtree of s.

Next, we check if the root nodes of s and t are the same using the isSameTree function. If they are the same, then t is a subtree of s.

If the root nodes of s and t are not the same, then t may be a subtree of the left subtree or the right subtree of s. We recursively call the isSubtree function on the left and right subtrees of s.

In the isSameTree function, we first check if s and t are both empty. If they are both empty, then they are the same.

If one of s or t is empty but the other is not, then they are not the same. If the values of the root nodes of s and t are different, then they are not the same.

If the values of the root nodes of s and t are the same, then we recursively check if their left and right subtrees are the same.

This solution has a time complexity of O(m*n) in the worst case, where m and n are the number of nodes in s and t, respectively. This is because we need to check if t is a subtree of each node in s. However, in practice, the time complexity is much lower because we can usually prune the search early.

Step by Step Implementation For Subtree Of Another Tree

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        //check if t is a subtree of s
        if(s == null) return false;
        if(isSameTree(s,t)) return true;
        return isSubtree(s.left,t) || isSubtree(s.right,t);
    }
    
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //check if p and q are the same tree
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        if(p.val != q.val) return false;
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

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 1:
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.
Example 2:
Given tree s:

3
/ \
4   5
/ \
1   2
/
0
Given tree t:
4
/ \
1   2
Return false.

def isSubtree(s, t):
    # base case: 
    if not s: 
        return False
    if isSameTree(s, t): 
        return True
    # if the tree with root as current node doesn't match then 
    # try left and right subtrees one by one 
    return isSubtree(s.left, t) or isSubtree(s.right, t) 
  
# A tree is subtree of another tree if both with same value 
# and subtree structures 
def isSameTree(x, y): 
    # base case 
    if not x and not y: 
        return True
    # if one of the trees is empty 
    if not x or not y: 
        return False
    # if value doesn't match 
    if x.val != y.val: 
        return False
    # if values match recursively check for left and right subtrees 
    return isSameTree(x.left, y.left) and isSameTree(x.right, y.right)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} s
 * @param {TreeNode} t
 * @return {boolean}
 */
var isSubtree = function(s, t) {
    // edge case - if either tree is empty, then
    // t can't be a subtree of s
    if (!s || !t) {
        return false;
    }
    
    // if the root values of the two trees are equal,
    // then check if the rest of the trees are equal
    if (s.val === t.val) {
        return isEqual(s, t);
    }
    
    // if the root values are not equal, check if t is a
    // subtree of s.left or s.right
    return isSubtree(s.left, t) || isSubtree(s.right, t);
};

// helper function to check if two trees are equal
var isEqual = function(s, t) {
    // if both trees are null, then they are equal
    if (!s && !t) {
        return true;
    }
    
    // if one tree is null and the other isn't, then they are not equal
    if (!s || !t) {
        return false;
    }
    
    // if the root values are not equal, then the trees are not equal
    if (s.val !== t.val) {
        return false;
    }
    
    // check if the left and right subtrees are equal
    return isEqual(s.left, t.left) && isEqual(s.right, t.right);
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        // Base case
        if (s == nullptr) {
            return false;
        }
        if (t == nullptr) {
            return true;
        }
        
        // Recursive case
        if (isIdentical(s, t)) {
            return true;
        }
        return isSubtree(s->left, t) || isSubtree(s->right, t);
    }
    
    bool isIdentical(TreeNode* s, TreeNode* t) {
        // Base case
        if (s == nullptr && t == nullptr) {
            return true;
        }
        if (s == nullptr || t == nullptr) {
            return false;
        }
        
        // Recursive case
        if (s->val != t->val) {
            return false;
        }
        return isIdentical(s->left, t->left) && isIdentical(s->right, t->right);
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public bool IsSubtree(TreeNode s, TreeNode t) {
        if(s == null) return false;
        if(s.val == t.val && IsSameTree(s,t)) return true;
        return IsSubtree(s.left, t) || IsSubtree(s.right, t);
    }
    
    public bool IsSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        if(p.val != q.val) return false;
        return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
    }
}