Same Tree

🏠 ⬅️ ➡️

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3] Output: true

Example 2:

Input: p = [1,2], q = [1,null,2] Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2] Output: false

Constraints:

  • The number of nodes in both trees is in the range [0, 100].
  • -104 <= Node.val <= 104
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 3
    type(node), target :: p(n)
    type(node), target :: q(n)

    call init_nodes(p)
    call init_nodes(q)

    print '(L1)', same_tree(p, q)

contains

    subroutine init_nodes(nodes)
        implicit none
        type(node), intent(inout) :: nodes(:)
        integer :: i

        do i = 1, size(nodes)
            allocate(nodes(i)%left)
            allocate(nodes(i)%right)
            nodes(i)%val = i
        end do
    end subroutine init_nodes

    logical function same_tree(p, q) result(same)
        implicit none
        type(node), intent(in) :: p(:)
        type(node), intent(in) :: q(:)
        integer :: i

        same = .true.

        do i = 1, size(p)
            if (associated(p(i)%left)) then
                if (.not. associated(q(i)%left)) return
                same = same .and. same_tree(p(i)%left, q(i)%left)
            else
                if (associated(q(i)%left)) return
            end if

            if (associated(p(i)%right)) then
                if (.not. associated(q(i)%right)) return
                same = same .and. same_tree(p(i)%right, q(i)%right)
            else
                if (associated(q(i)%right)) return
            end if

            if (p(i)%val /= q(i)%val) return
        end do
    end function same_tree

end program main

type node
    integer :: val
    class(node), pointer :: left => null()
    class(node), pointer :: right => null()
end type node
❌ Compiled
❌ Executed
❌ Correct 
module same_tree

contains

function is_same_tree(p, q) result(same)

! Declare the variables
integer :: p, q
logical :: same

! Check if the roots are the same
if (p == q) then
    same = .true.
else
    same = .false.
endif

! Check if the left subtrees are the same
if (associated(p%left) .and. associated(q%left)) then
    if (is_same_tree(p%left, q%left)) then
        same = .true.
    else
        same = .false.
    endif
elseif (associated(p%left) .or. associated(q%left)) then
    same = .false.
endif

! Check if the right subtrees are the same
if (associated(p%right) .and. associated(q%right)) then
    if (is_same_tree(p%right, q%right)) then
        same = .true.
    else
        same = .false.
    endif
elseif (associated(p%right) .or. associated(q%right)) then
    same = .false.
endif

end function is_same_tree

end module same_tree

program main

use same_tree

implicit none

! Declare the variables
type(tree_node), pointer :: p, q
logical :: same

! Create the first tree
p = tree_node(1, tree_node(2, tree_node(3), null()), null())

! Create the second tree
q = tree_node(1, tree_node(2, tree_node(3), null()), null())

! Check if the trees are the same
same = is_same_tree(p, q)

! Print the result
if (same) then
    write (*,*) "The trees are the same"
else
    write (*,*) "The trees are not the same"
endif

end program main

! Define the tree node structure
type tree_node
    integer :: val
    type(tree_node), pointer :: left, right
end type tree_node
🌐 Data from online sources 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_same_tree(p, q):
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    if p.val != q.val:
        return False
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

The algorithm used is a recursive depth-first traversal of both trees. It will compare the nodes at each level of the tree, and return false if the nodes have different values or if one node is missing in one of the trees. The algorithm will only return true if all nodes in both trees are the same.

At each level, the function checks if both nodes are null, indicating we've reached the end of both trees and they must be the same. Then it checks if either node is null, indicating that one tree is missing a node and they cannot be the same. If both nodes have the same value, we then recursively check their left and right children. If both children are the same, the function returns true. If at any point nodes are found to be different, the function returns false.

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

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (p == nullptr && q == nullptr) {
        return true;
    }
    if (p == nullptr || q == nullptr) {
        return false;
    }
    if (p->val != q->val) {
        return false;
    }
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

The algorithm used is a recursive depth-first traversal of both trees. It will compare the nodes at each level of the tree, and return false if the nodes have different values or if one node is missing in one of the trees. The algorithm will only return true if all nodes in both trees are the same.

At each level, the function checks if both nodes are null, indicating we've reached the end of both trees and they must be the same. Then it checks if either node is null, indicating that one tree is missing a node and they cannot be the same. If both nodes have the same value, we then recursively check their left and right children. If both children are the same, the function returns true. If at any point nodes are found to be different, the function returns false.