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.

Examples

Example 1:

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

Output: true

Example 2:

Input: root = [1,2,3,4,5,null,null,6], subRoot = [2,4,5]

Output: false

Constraints

• 1 <= The number of nodes in both trees <= 100.
• -100 <= root.val, subRoot.val <= 100

You should aim for a solution as good or better than O(m * n) time and O(m + n) space, where n and m are the number of nodes in root and subRoot, respectively.

Solution

For every node in the tree, we check if the subtree rooted at the current node matches the other tree. One recursion function checks every node in the tree, another checks for equality of the subtrees.

/**
 * 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* root, TreeNode* subRoot) {
        if (!subRoot) { return true; }
        std::function<bool(TreeNode*, TreeNode*)> runner_equal;
        runner_equal = [&](TreeNode*lhs, TreeNode*rhs) -> bool {
            // Both are nullptr
            if (!lhs && !rhs) { return true; }
            // One nullptr and other is not
            if ((!lhs && rhs) || (lhs && !rhs)) { return false; }
            // Both contain payloads, compare
            if (lhs->val != rhs->val) { return false; }
            // Check left subtree and right subtree
            return runner_equal(lhs->left, rhs->left) && runner_equal(lhs->right, rhs->right);
        };
 
        // Walk tree as DFS and check each node for equal subtree
        std::function<bool(TreeNode*)> runner_search;
        runner_search = [&](TreeNode *node) -> bool {
            if (!node) { return false; }
            if (runner_equal(node, subRoot)) {
                return true;
            }
            return runner_search(node->left) || runner_search(node->right);
        };
 
        return runner_search(root);
    }
};