Subtree of Another Tree

🏠 ⬅️ ➡️

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].
  • -104 <= root.val <= 104
  • -104 <= subRoot.val <= 104
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
    implicit none
    integer, parameter :: n = 7
    real(kind=DP), dimension(n) :: root = [3._DP, 4._DP, 5._DP, 1._DP, &
                                           2._DP, -1._DP, -2._DP]
    real(kind=DP), dimension(n) :: subRoot = [4._DP, 1._DP, 2._DP]
    logical :: result

    print '(L1)', hasSubtree(root, subRoot)

contains

    function hasSubtree(root, subRoot) result(res)
        real(kind=DP), intent(in) :: root(:), subRoot(:)
        logical :: res

        res = .false.

        call hasSubtreeRecursive(root, subRoot, 1, res)

    end function hasSubtree

    recursive subroutine hasSubtreeRecursive(root, subRoot, idx, found)
        real(kind=DP), intent(in) :: root(:), subRoot(:)
        integer, value :: idx
        logical, intent(out) :: found
        integer :: i

        if (idx > size(root)) then
            return
        end if

        if (root(idx) == subRoot(1)) then
            found = .true.
            do i = 2, size(subRoot)
                if (root(idx+i-1) /= subRoot(i)) then
                    found = .false.
                    exit
                end if
            end do
            if (.not. found) then
                return
            end if
        end if

        call hasSubtreeRecursive(root, subRoot, idx+1, found)

        if (.not. found) then
            call hasSubtreeRecursive(root, subRoot, idx+size(root)-idx+1, found)
        end if

    end subroutine hasSubtreeRecursive

end program main
❌ Compiled
❌ Executed
❌ Correct 
module BinaryTree
    implicit none

    type :: Node
        integer :: val
        type(Node), pointer :: left
        type(Node), pointer :: right
    end type Node

    interface
        function is_same_tree(root, subRoot) result(same)
            type(Node), pointer, intent(in) :: root, subRoot
            logical :: same
        end function is_same_tree
    end interface

contains

    function is_subtree(root, subRoot) result(same)
        type(Node), pointer, intent(in) :: root, subRoot
        logical :: same

        same = is_same_tree(root, subRoot)

    end function is_subtree

    function is_same_tree(root, subRoot) result(same)
        type(Node), pointer, intent(in) :: root, subRoot
        logical :: same

        if (associated(root, subRoot)) then
            same = .true.
        else if (associated(root)) then
            same = is_same_tree(root%left, subRoot) .or. is_same_tree(root%right, subRoot)
        else
            same = .false.
        end if

    end function is_same_tree

end module BinaryTree

program main
    use BinaryTree
    implicit none

    type(Node), pointer :: root, subRoot
    logical :: same

    ! Example 1
    root => Node(val=3, left=Node(val=4, left=Node(val=1, left=Node(val=2))), right=Node(val=5))
    subRoot => Node(val=4, left=Node(val=1, left=Node(val=2)))
    same = is_subtree(root, subRoot)
    write (*,*) "Example 1: ", same

    ! Example 2
    root => Node(val=3, left=Node(val=4, left=Node(val=1, left=Node(val=2))), right=Node(val=5))
    subRoot => Node(val=4, left=Node(val=1, left=Node(val=2, left=Node(val=0))))
    same = is_subtree(root, subRoot)
    write (*,*) "Example 2: ", same

end program main
🌐 Data from online sources 
class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function isSubtree(root, subRoot) {
    if (root === null) return false;
    if (isIdentical(root, subRoot)) return true;
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}

function isIdentical(n1, n2) {
    if (n1 === null || n2 === null) return n1 === n2;
    if (n1.val !== n2.val) return false;
    return isIdentical(n1.left, n2.left) && isIdentical(n1.right, n2.right);
}

The algorithm checks if subRoot is a subtree of root by first looking whether the two trees have the same root node. If they do, it checks whether the substructures are also identical. If they are not, then subRoot is not a subtree at this level, and the algorithm looks further down the left and right branches of root. This is done by returning the logical OR between the result of checking left and right branches.

The helper function isIdentical checks whether the two given trees have the same structure and node values, by comparing the current nodes and then recursively traversing the left and right substructures. If a None value for a node is found, the two nodes are identical if they are both None. Otherwise, if the node values differ, the trees are not identical.

🌐 Data from online sources 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};

bool isSubtree(TreeNode* root, TreeNode* subRoot) {
    if (root == nullptr) return false;
    if (isIdentical(root, subRoot)) return true;
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

bool isIdentical(TreeNode* n1, TreeNode* n2) {
    if (n1 == nullptr || n2 == nullptr) return n1 == n2;
    if (n1->val != n2->val) return false;
    return isIdentical(n1->left, n2->left) && isIdentical(n1->right, n2->right);
}

The algorithm checks if subRoot is a subtree of root by first looking whether the two trees have the same root node. If they do, it checks whether the substructures are also identical. If they are not, then subRoot is not a subtree at this level, and the algorithm looks further down the left and right branches of root. This is done by returning the logical OR between the result of checking left and right branches.

The helper function isIdentical checks whether the two given trees have the same structure and node values, by comparing the current nodes and then recursively traversing the left and right substructures. If a None value for a node is found, the two nodes are identical if they are both None. Otherwise, if the node values differ, the trees are not identical.