Symmetric Tree

🏠 ⬅️ ➡️

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3] Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3] Output: false

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • -100 <= Node.val <= 100

Follow up: Could you solve it both recursively and iteratively?

Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, output_unit
    implicit none
    integer, parameter :: unit_in = input_unit, unit_out = output_unit
    type(tree_node), pointer :: root
    logical :: result

    call read_tree(unit=unit_in, root=root)
    result = check_mirror(root)
    write (unit=output_unit, fmt='(L1)') result

contains

    function check_mirror(root) result(result)
        class(tree_node), pointer, intent(in) :: root
        logical :: result
        class(tree_node), pointer :: left, right

        if (.not. associated(root)) then
            result = .true.
            return
        end if

        left => root%left
        right => root%right

        ! Check if left subtree is a mirror of right subtree
        if (associated(left)) then
            result = check_mirror(left)
            if (.not. result) return
        else if (associated(right)) then
            result = .false.
            return
        end if

        ! Check if right subtree is a mirror of left subtree
        if (associated(right)) then
            result = check_mirror(right)
            if (.not. result) return
        else if (associated(left)) then
            result = .false.
            return
        end if

        ! If we reach this point, both subtrees are mirrors of each other
        result = .true.

    end function check_mirror

    subroutine read_tree(unit, root)
        integer, intent(in) :: unit
        type(tree_node), pointer, intent(out) :: root
        integer :: value

        read (unit=unit, fmt=*) value
        if (value == -1) then
            nullify(root)
        else
            allocate(root)
            root%val = value
            call read_tree(unit, root%left)
            call read_tree(unit, root%right)
        end if

    end subroutine read_tree

end program main

type :: tree_node
    integer :: val
    class(tree_node), pointer :: left => null(), right => null()
end type tree_node
❌ Compiled
❌ Executed
❌ Correct 
module BinaryTree
    implicit none
    private
    public :: Node, is_mirror

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

contains

    function is_mirror(root) result(is_mirrored)
        type(Node), pointer, intent(in) :: root
        logical :: is_mirrored

        is_mirrored = is_mirror_recursive(root)
    end function is_mirror

    recursive function is_mirror_recursive(root) result(is_mirrored)
        type(Node), pointer, intent(in) :: root
        logical :: is_mirrored

        if (.not. associated(root)) then
            is_mirrored = .true.
            return
        end if

        is_mirrored = (root%val == root%left%val) .and. (root%val == root%right%val) .and. &
            is_mirror_recursive(root%left) .and. is_mirror_recursive(root%right)
    end function is_mirror_recursive
end module BinaryTree

program main
    use BinaryTree
    implicit none

    type(Node), pointer :: root
    logical :: is_mirrored

    ! Example 1
    root => Node(val=1, left=Node(val=2, left=Node(val=2), right=Node(val=3)), &
        right=Node(val=4, left=Node(val=4), right=Node(val=3)))
    is_mirrored = is_mirror(root)
    write (*,*) "Example 1: ", is_mirrored

    ! Example 2
    root => Node(val=1, left=Node(val=2, left=Node(val=2), right=Node(val=3)), &
        right=Node(val=4, left=Node(val=4), right=Node(val=3)))
    is_mirrored = is_mirror(root)
    write (*,*) "Example 2: ", is_mirrored
end program main
🌐 Data from online sources 
def isSymmetric(root):
    return checkSymmetry(root, root)

def checkSymmetry(node1, node2):
    if not node1 and not node2:
        return True
    if not node1 or not node2:
        return False
    return (node1.val == node2.val) and checkSymmetry(node1.right, node2.left) and checkSymmetry(node1.left, node2.right)

The algorithm works by comparing the left subtree and right subtree of the root node. It uses a helper function, 'checkSymmetry()', which takes two nodes as its arguments. The base cases for this helper function are when both nodes are null, in which case the function should return true, or when one of the nodes is null, in which case the function should return false.

The function then checks whether the values of both nodes are equal and continues to call itself recursively, but with the arguments changed to evaluate the left subtree and right subtree symmetrically. If the left and right subtrees have symmetric nodes, the function will return true; otherwise, it will return false.

The recursive calls in the helper function flip the direction of traversal for both subtrees to ensure that the subtrees are compared symmetrically. In each recursive call, the appropriate child nodes are visited in opposite directions to make sure they can be properly compared.

🌐 Data from online sources 
bool isSymmetric(TreeNode* root) {
    return checkSymmetry(root, root);
}

bool checkSymmetry(TreeNode* node1, TreeNode* node2) {
    if (!node1 && !node2) return true;
    if (!node1 || !node2) return false;
    return (node1->val == node2->val) && checkSymmetry(node1->right, node2->left) && checkSymmetry(node1->left, node2->right);
}

The algorithm works by comparing the left subtree and right subtree of the root node. It uses a helper function, 'checkSymmetry()', which takes two nodes as its arguments. The base cases for this helper function are when both nodes are null, in which case the function should return true, or when one of the nodes is null, in which case the function should return false.

The function then checks whether the values of both nodes are equal and continues to call itself recursively, but with the arguments changed to evaluate the left subtree and right subtree symmetrically. If the left and right subtrees have symmetric nodes, the function will return true; otherwise, it will return false.

The recursive calls in the helper function flip the direction of traversal for both subtrees to ensure that the subtrees are compared symmetrically. In each recursive call, the appropriate child nodes are visited in opposite directions to make sure they can be properly compared.