Increasing Order Search Tree

šŸ  ā¬…ļø āž”ļø

Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

Example 1:

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

Example 2:

Input: root = [5,1,7] Output: [1,null,5,null,7]

Constraints:

  • The number of nodes in the given tree will be in the range [1, 100].
  • 0 <= Node.val <= 1000
Note: This problem is from LeetCode.
āŒ Compiled
āŒ Executed
āŒ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, iostat_end
    implicit none
    integer, parameter :: unit_in = 10, unit_out = 20
    character(len=256) :: filename
    type(error_type), allocatable :: err
    type(tree_node), pointer :: root

    ! Read input from file
    write (unit=unit_out, fmt='(A)') 'Enter input filename:'
    read (unit=unit_in, fmt='(A)', iostat=err%stat, iomsg=err%msg, &
          iolength=err%n) filename
    if (err%stat /= 0) then
        write (unit=error_unit, fmt='(2A)') 'error: ', trim(err%msg)
        stop 1
    end if
    open (newunit=unit_in, file=filename, status='old', &
          action='read', access='stream', form='unformatted', &
          iostat=err%stat, iomsg=err%msg)
    if (err%stat /= 0) then
        write (unit=error_unit, fmt='(2A)') 'error: ', trim(err%msg)
        stop 1
    end if
    call read_tree(unit_in, root)
    close (unit=unit_in)

    ! Rearrange tree
    call rearrange_tree(root)

    ! Write output to stdout
    call print_tree(root, unit_out)

contains

    subroutine read_tree(unit, root)
        implicit none
        integer, intent(in) :: unit
        type(tree_node), pointer, intent(out) :: root
        class(tree_node), pointer :: current
        integer :: stat

        allocate (current)
        current => root
        do
            read (unit=unit, fmt=*, iostat=stat) current%val
            if (stat == iostat_end) exit
            allocate (current%right)
            current => current%right
        end do
        nullify (current%right)
    end subroutine read_tree

    subroutine rearrange_tree(root)
        implicit none
        type(tree_node), pointer, intent(inout) :: root
        type(tree_node), pointer :: current, next

        current => root
        do while (associated(current))
            if (associated(current%left)) then
                next => current%left
                current%left => null()
                current => next
            else
                next => current%right
                current%right => null()
                current => next
            end if
        end do
    end subroutine rearrange_tree

    subroutine print_tree(root, unit)
        implicit none
        type(tree_node), pointer, intent(in) :: root
        integer, intent(in) :: unit
        class(tree_node), pointer :: current

        current => root
        do while (associated(current))
            write (unit=unit, fmt='(I0)') current%val
            if (associated(current%left)) then
                current => current%left
            else if (associated(current%right)) then
                current => current%right
            else
                exit
            end if
        end do
    end subroutine print_tree

end program main

type :: tree_node
    integer :: val
    type(tree_node), pointer :: left => null(), right => null()
end type tree_node
āŒ Compiled
āŒ Executed
āŒ Correct 
module BST

! Declare the node structure
type :: Node
    integer :: val
    type(Node), pointer :: left
    type(Node), pointer :: right
end type

contains

! Function to rearrange the tree
recursive function rearrange(root) result(new_root)
    type(Node), pointer :: root
    type(Node), pointer :: new_root
    type(Node), pointer :: current
    type(Node), pointer :: previous

    ! Base case: if the root is null, return null
    if (.not. associated(root)) then
        nullify(new_root)
        return
    end if

    ! Recursive case: rearrange the left subtree
    current => root
    previous => null()
    call rearrange(current%left, new_root)

    ! Connect the previous node to the current node
    if (associated(previous)) then
        previous%right => current
    end if

    ! Connect the current node to the right subtree
    current%left => null()
    call rearrange(current%right, current%right)

    ! Return the new root
    new_root => current

end function

end module

program main
    use BST
    implicit none

    ! Test case 1
    type(Node), pointer :: root
    type(Node), pointer :: new_root
    integer, dimension(10) :: values = [5, 3, 6, 2, 4, 0, 8, 1, 0, 7, 9]

    ! Create the tree
    root => null()
    do i = 1, size(values)
        call insert(root, values(i))
    end do

    ! Rearrange the tree
    new_root => rearrange(root)

    ! Print the tree
    call print_tree(new_root)

    ! Test case 2
    root => null()
    call insert(root, 5)
    call insert(root, 1)
    call insert(root, 7)

    ! Rearrange the tree
    new_root => rearrange(root)

    ! Print the tree
    call print_tree(new_root)

contains

! Function to insert a value in the tree
recursive subroutine insert(root, val)
    type(Node), pointer :: root
    integer :: val
    type(Node), pointer :: current

    ! Base case: if the root is null, create a new node
    if (.not. associated(root)) then
        allocate(root)
        root%val = val
        root%left => null()
        root%right => null()
        return
    end if

    ! Recursive case: insert the value in the left or right subtree
    current => root
    if (val < current%val) then
        call insert(current%left, val)
    else
        call insert(current%right, val)
    end if

end subroutine

! Function to print the tree
recursive subroutine print_tree(root)
    type(Node), pointer :: root
    type(Node), pointer :: current

    ! Base case: if the root is null, return
    if (.not. associated(root)) then
        return
    end if

    ! Print the left subtree
    current => root
    call print_tree(current%left)

    ! Print the current node
    write (*,*) current%val

    ! Print the right subtree
    call print_tree(current%right)

end subroutine

end program
šŸŒ Data from online sources 
def is_prime(n):
    if n <= 1:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def is_palindrome(n):
    return str(n) == str(n)[::-1]

def prime_palindrome(n):
    while True:
        if is_prime(n) and is_palindrome(n):
            return n
        n += 1

The algorithm consists of three functions: isPrime, isPalindrome, and primePalindrome. The first function, isPrime, checks if a given number is prime by iterating from 2 to the square root of the number and checking if the number has any divisors. If not, the function returns true, indicating prime.

The second function, isPalindrome, checks if a given number is a palindrome by converting the number to a string and then reversing the string. If the original and reversed strings are the same, the function returns true, indicating a palindrome.

The main function, primePalindrome, takes an integer n as input and iterates from n onward, checking if each number is both prime and a palindrome using the isPrime and isPalindrome helper functions. When a number is found to be both prime and a palindrome, it is returned as the answer.

The algorithm has a complexity of O(sqrt(n) * n) in the worst case because isPrime has a complexity of O(sqrt(n)) and both isPalindrome and primePalindrome have complexities of O(n).

šŸŒ Data from online sources 
bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

bool isPalindrome(int n) {
    int rev = 0, orig = n;
    while (n > 0) {
        rev = rev * 10 + n % 10;
        n /= 10;
    }
    return orig == rev;
}

int primePalindrome(int n) {
    while (true) {
        if (isPrime(n) && isPalindrome(n)) return n;
        n++;
    }
}

The algorithm consists of three functions: isPrime, isPalindrome, and primePalindrome. The first function, isPrime, checks if a given number is prime by iterating from 2 to the square root of the number and checking if the number has any divisors. If not, the function returns true, indicating prime.

The second function, isPalindrome, checks if a given number is a palindrome by converting the number to a string and then reversing the string. If the original and reversed strings are the same, the function returns true, indicating a palindrome.

The main function, primePalindrome, takes an integer n as input and iterates from n onward, checking if each number is both prime and a palindrome using the isPrime and isPalindrome helper functions. When a number is found to be both prime and a palindrome, it is returned as the answer.

The algorithm has a complexity of O(sqrt(n) * n) in the worst case because isPrime has a complexity of O(sqrt(n)) and both isPalindrome and primePalindrome have complexities of O(n).