Univalued Binary Tree

🏠 ⬅️ ➡️

A binary tree is uni-valued if every node in the tree has the same value.

Given the root of a binary tree, return true if the given tree is uni-valued, or false otherwise.

Example 1:

Input: root = [1,1,1,1,1,null,1] Output: true

Example 2:

Input: root = [2,2,2,5,2] Output: false

Constraints:

  • The number of nodes in the tree is in the range [1, 100].
  • 0 <= Node.val < 100
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    ! Solves the problem:
    ! A binary tree is uni-valued if every node in the tree has the same value.
    ! Given the root of a binary tree, return true if the given tree is uni-valued, or false otherwise.
    use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
    implicit none
    integer, parameter :: unit_in = 10, unit_out = 20
    character(len=20) :: filename

    type :: TreeNode
        real(kind=DP), pointer :: val => null()
        type(TreeNode), pointer :: left => null(), right => null()
    end type TreeNode

    type(TreeNode), pointer :: root

    logical :: result

    write (unit=unit_out, fmt='(A)') 'Enter filename:'
    read (unit=unit_in, fmt='(A)') filename
    open (newunit=unit_in, file=filename, status='old', action='read', &
          iostat=result, iomsg=filename)
    if (result /= 0) then
        write (unit=error_unit, fmt='(2A)') 'error: cannot open file "', trim(filename), '"'
        stop 1
    end if
    call parse_tree(unit_in, root)
    close (unit=unit_in)

    result = is_uni_valued(root)
    write (unit=unit_out, fmt='(L1)') result

contains

    subroutine parse_tree(unit_in, root)
        implicit none
        integer, intent(in) :: unit_in
        type(TreeNode), pointer, intent(out) :: root
        class(*), allocatable :: tmp
        allocate (tmp)
        call parse_node(unit_in, tmp)
        select type (tmp)
            type is (real(kind=DP))
                allocate (root)
                root%val => tmp
            type is (TreeNode)
                allocate (root)
                root%left => tmp
            class default
                error stop 'parse_tree: invalid node type'
        end select
    end subroutine parse_tree

    subroutine parse_node(unit_in, node)
        implicit none
        integer, intent(in) :: unit_in
        class(*), allocatable, intent(out) :: node
        character(len=20) :: token
        read (unit=unit_in, fmt=*, iostat=result) token
        if (result /= 0) then
            deallocate (node)
            return
        end if
        select case (token)
            case ('[')
                allocate (TreeNode::node)
                call parse_node(unit_in, node%left)
                call parse_node(unit_in, node%right)
            case (']')
                deallocate (node)
            case default
                allocate (real(kind=DP)::node)
                read (unit=token, fmt=*) node
        end select
    end subroutine parse_node

    function is_uni_valued(root) result(res)
        implicit none
        type(TreeNode), pointer, intent(in) :: root
        logical :: res
        real(kind=DP) :: val
        res = .true.
        if (.not. associated(root)) return
        val = root%val
        if (.not. is_uni_valued(root%left)) then
            res = .false.
            return
        end if
        if (.not. is_uni_valued(root%right)) then
            res = .false.
            return
        end if
        if (abs(val - root%left%val) > epsilon(val)) then
            res = .false.
            return
        end if
        if (abs(val - root%right%val) > epsilon(val)) then
            res = .false.
            return
        end if
    end function is_uni_valued

end program main
❌ Compiled
❌ Executed
❌ Correct 
module BinaryTreeUniValued
    implicit none
    private
    public :: is_uni_valued

contains

    function is_uni_valued(root) result(is_uni)
        type(Node), pointer, intent(in) :: root
        logical :: is_uni

        is_uni = is_uni_valued_helper(root)
    end function is_uni_valued

    recursive function is_uni_valued_helper(node) result(is_uni)
        type(Node), pointer, intent(in) :: node
        logical :: is_uni

        if (.not. associated(node)) then
            is_uni = .true.
        else
            is_uni = is_uni_valued_helper(node%left) .and. &
                     is_uni_valued_helper(node%right) .and. &
                     node%val == node%left%val .and. &
                     node%val == node%right%val
        end if
    end function is_uni_valued_helper

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

program test_binary_tree_uni_valued
    use BinaryTreeUniValued
    implicit none

    type(Node) :: root
    logical :: is_uni

    ! Example 1
    root = Node(1, Node(1, Node(1, Node(1, Node(1, Node(1, null(), null()), null()), null()), null()), null()), null())
    is_uni = is_uni_valued(root)
    write (*, '(A, L1)') 'Example 1: ', is_uni

    ! Example 2
    root = Node(2, Node(2, Node(2, Node(2, Node(2, null(), null()), null()), null()), null()), null())
    is_uni = is_uni_valued(root)
    write (*, '(A, L1)') 'Example 2: ', is_uni
end program test_binary_tree_uni_valued
🌐 Data from online sources 
def num_unique_emails(emails):
    unique_emails = set()

    for email in emails:
        local_name, domain_name = email.split("@")
        local_name = local_name.split("+")[0]
        local_name = local_name.replace(".", "")

        unique_emails.add(local_name + "@" + domain_name)

    return len(unique_emails)

The algorithm iterates through each email in the input array/list. For each email, the local name and domain name are separated based on the '@' sign. Next, the '+' sign is considered, and everything after the first '+' sign is ignored in the local name. Then, all the '.' characters in the local name are removed. Finally, the processed local name and domain name are combined and added to a set, which will hold unique email addresses. After processing all the email addresses, the size of the set represents the number of unique email addresses that actually receive mails.

🌐 Data from online sources 
#include <string>
#include <vector>
#include <set>

int numUniqueEmails(std::vector<std::string>& emails) {
    std::set<std::string> unique_emails;

    for (auto& email : emails) {
        std::string local_name, domain_name;
        bool at_sign_found = false, plus_sign_found = false;

        for (char c : email) {
            if (!at_sign_found) {
                if (c == '+') plus_sign_found = true;
                else if (c == '@') at_sign_found = true;
                else if (!plus_sign_found && c != '.') local_name += c;
            }
            else domain_name += c;
        }

        unique_emails.insert(local_name + "@" + domain_name);
    }

    return unique_emails.size();
}

The algorithm iterates through each email in the input array/list. For each email, the local name and domain name are separated based on the '@' sign. Next, the '+' sign is considered, and everything after the first '+' sign is ignored in the local name. Then, all the '.' characters in the local name are removed. Finally, the processed local name and domain name are combined and added to a set, which will hold unique email addresses. After processing all the email addresses, the size of the set represents the number of unique email addresses that actually receive mails.