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.

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

Constraints:

The number of nodes in the root tree is in the range [1, 2000].
The number of nodes in the subRoot tree is in the range [1, 1000].
-10⁴ <= root.val <= 10⁴
-10⁴ <= subRoot.val <= 10⁴

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} subRoot
 * @return {boolean}
 */
var isSubtree = function(root, subRoot) {
    if (!root) {
        return false;
    } else if (isSame(root, subRoot)) {
        return true;
    } else {
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }
};

var isSame = function(root, subRoot) {
    if (!root && !subRoot) {
        return true;
    } else if (root?.val === subRoot?.val) {
        return isSame(root.left, subRoot.left) && isSame(root.right, subRoot.right);
    } else {
        return false;
    }
};

We will implement a DFS solution. We try every node in root as the potential root of the subtree that matches subRoot, and check if the two trees are indeed the same (ie. does there exist a subtree of root that is the same as the tree subRoot).

Problem​

Solution​

Problem

Solution