Invert Binary Tree

🏠 ⬅️ ➡️

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1]

Example 2:

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

Example 3:

Input: root = [] Output: []

Constraints:

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

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

    type(TreeNode), target :: root
    type(TreeNode), pointer :: current
    integer :: i

    ! Examples
    call invertTree(root)
    print "(A)", "Example 1:"
    do i = 1, size(root%left)
        print "(I0)", root%left(i)%val
    end do
    print *, ""
    do i = 1, size(root%right)
        print "(I0)", root%right(i)%val
    end do
    print *, ""

    call invertTree(root)
    print "(A)", "Example 2:"
    do i = 1, size(root%left)
        print "(I0)", root%left(i)%val
    end do
    print *, ""
    do i = 1, size(root%right)
        print "(I0)", root%right(i)%val
    end do
    print *, ""

    call invertTree(root)
    print "(A)", "Example 3:"
    do i = 1, size(root%left)
        print "(I0)", root%left(i)%val
    end do
    print *, ""
    do i = 1, size(root%right)
        print "(I0)", root%right(i)%val
    end do
    print *, ""

contains

    subroutine invertTree(root)
        ! Invert the tree and return its root
        implicit none
        type(TreeNode), intent(inout) :: root
        type(TreeNode), pointer :: current
        type(TreeNode), pointer :: temp

        if (associated(root)) then
            current => root
            do while (associated(current))
                ! Swap the left and right pointers
                temp => current%left
                current%left => current%right
                current%right => temp

                ! Recursively invert the left and right subtrees
                call invertTree(current%left)
                call invertTree(current%right)

                ! Move to the next node
                current => current%right
            end do
        end if
    end subroutine invertTree

end program main
❌ Compiled
❌ Executed
❌ Correct 
!InvertBinaryTree

!This function takes a pointer to the root of a binary tree and returns a pointer to the inverted tree.

!Definition of the Node structure:
type Node
    integer :: val
    type(Node), pointer :: left
    type(Node), pointer :: right
end type Node

interface
    function invertTree(root) result(newRoot)
        type(Node), pointer :: root
        type(Node), pointer :: newRoot
    end function invertTree
end interface

contains

function invertTree(root) result(newRoot)
    type(Node), pointer :: root
    type(Node), pointer :: newRoot
    type(Node), pointer :: current
    type(Node), pointer :: newCurrent

    !Create a new root node
    allocate(newRoot)
    newRoot%val = root%val
    newRoot%left => null()
    newRoot%right => null()

    !Traverse the tree and invert the links
    current => root
    do while (associated(current))
        !Create a new node for the current node
        allocate(newCurrent)
        newCurrent%val = current%val
        newCurrent%left => null()
        newCurrent%right => null()

        !Invert the links
        if (associated(current%left)) then
            newCurrent%right => invertTree(current%left)
        end if
        if (associated(current%right)) then
            newCurrent%left => invertTree(current%right)
        end if

        !Update the current node
        current => newCurrent
    end do

    !Return the inverted tree
    newRoot => current
end function invertTree

end

!Test the function with the given examples
program test
    implicit none

    !Declare the variables
    type(Node), pointer :: root
    type(Node), pointer :: newRoot

    !Create the root node
    allocate(root)
    root%val = 4
    root%left => null()
    root%right => null()

    !Invert the tree
    newRoot => invertTree(root)

    !Print the result
    write (*,*) "Inverted tree: ", newRoot%val

    !Free the memory
    deallocate(root)
    deallocate(newRoot)

    !Create the root node
    allocate(root)
    root%val = 2
    root%left => null()
    root%right => null()

    !Invert the tree
    newRoot => invertTree(root)

    !Print the result
    write (*,*) "Inverted tree: ", newRoot%val

    !Free the memory
    deallocate(root)
    deallocate(newRoot)

    !Create the root node
    allocate(root)
    root%val = 1
    root%left => null()
    root%right => null()

    !Invert the tree
    newRoot => invertTree(root)

    !Print the result
    write (*,*) "Inverted tree: ", newRoot%val

    !Free the memory
    deallocate(root)
    deallocate(newRoot)

    !Create the root node
    allocate(root)
    root%val = 3
    root%left => null()
    root%right => null()

    !Invert the tree
    newRoot => invertTree(root)

    !Print the result
    write (*,*) "Inverted tree: ", newRoot%val

    !Free the memory
    deallocate(root)
    deallocate(newRoot)

    !Create the root node
    allocate(root)
    root%val = 6
    root%left => null()
    root%right => null()

    !Invert the tree
    newRoot => invertTree(root)

    !Print the result
    write (*,*) "Inverted tree: ", newRoot%val

    !Free the memory
    deallocate(root)
    deallocate(newRoot)

    !Create the root node
    allocate(root)
    root%val = 9
    root%left => null()
    root%right => null()

    !Invert the tree
    newRoot => invertTree(root)

    !Print the result
🌐 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 invert_tree(root):
    if root is None:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root

This recursive algorithm traverses the tree in depth-first search order. At each visited node, we swap its left child with its right child. Then we apply the same process for the children.

🌐 Data from online sources 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) {
        return nullptr;
    }    
    TreeNode* temp = root->left;
    root->left = invertTree(root->right);
    root->right = invertTree(temp);
    return root;
}

This recursive algorithm traverses the tree in depth-first search order. At each visited node, we swap its left child with its right child. Then we apply the same process for the children.