Posts Subtree of Another Tree
Post
Cancel

Subtree of Another Tree

PROBLEM DESCRIPTION

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.

Leetcode

SOLUTION

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {

        if(root == null && subRoot == null) return false;
        if(root == null) return false; 

        boolean same = isSame(root, subRoot);
        return same || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);

    }

    public boolean isSame(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 isSame(p.left, q.left) && isSame(p.right, q.right);
    }

}
This post is licensed under CC BY 4.0 by the author.