Root Equals Sum of Children

🏠 ⬅️ ➡️

You are given the root of a binary tree that consists of exactly 3 nodes: the root, its left child, and its right child.

Return true if the value of the root is equal to the sum of the values of its two children, or false otherwise.

Example 1:

Input: root = [10,4,6] Output: true Explanation: The values of the root, its left child, and its right child are 10, 4, and 6, respectively. 10 is equal to 4 + 6, so we return true.

Example 2:

Input: root = [5,3,1] Output: false Explanation: The values of the root, its left child, and its right child are 5, 3, and 1, respectively. 5 is not equal to 3 + 1, so we return false.

Constraints:

  • The tree consists only of the root, its left child, and its right child.
  • -100 <= Node.val <= 100
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    ! This program solves the following problem:
    ! Given the root of a binary tree consisting of exactly 3 nodes, return true if the value of the root is equal to the sum of the values of its two children, or false otherwise.
    implicit none

    type :: node
        integer :: val
        type(node), pointer :: left, right
    end type

    type(node), target :: root
    type(node), pointer :: current
    logical :: result

    ! Examples
    call test([10, 4, 6], .true.)
    call test([5, 3, 1], .false.)

contains

    subroutine test(arr, expected)
        implicit none
        integer, intent(in) :: arr(:)
        logical, intent(in) :: expected
        type(node), pointer :: current

        allocate(current)
        current%val = arr(1)
        allocate(current%left)
        current%left%val = arr(2)
        allocate(current%right)
        current%right%val = arr(3)

        result = check_balanced(current)

        write(*, '(A, L1)') 'Test ', result == expected

        deallocate(current)
    end subroutine

    function check_balanced(root) result(result)
        implicit none
        type(node), pointer, intent(in) :: root
        logical :: result

        if (root%val /= root%left%val + root%right%val) then
            result = .false.
        else
            result = check_balanced(root%left) .and. check_balanced(root%right)
        end if
    end function
end program
❌ Compiled
❌ Executed
❌ Correct 
program EqualSum
      implicit none

      integer, parameter :: INF = 100

      type node
        integer :: val
        type(node), pointer :: left
        type(node), pointer :: right
      end type node

      type(node), pointer :: root

      logical :: is_equal

      ! Read the root node from the input
      read(*,*) root

      ! Check if the root node is null
      if (associated(root)) then
        ! Check if the root node is a leaf node
        if (associated(root%left) .and. associated(root%right)) then
          ! Check if the sum of the left and right child nodes is equal to the root node
          if (root%val == root%left%val + root%right%val) then
            is_equal = .true.
          else
            is_equal = .false.
          end if
        else
          ! Check if the root node is a leaf node
          if (associated(root%left) .or. associated(root%right)) then
            is_equal = .false.
          else
            is_equal = .true.
          end if
        end if
      else
        is_equal = .false.
      end if

      ! Print the result
      write(*,*) is_equal

      end program EqualSum

This script defines a `node` type to represent the nodes of the binary tree, and a `root` pointer to point to the root node of the tree. The `is_equal` variable is used to store the result of the comparison.

The script reads the root node from the input, and checks if it is null. If it is not null, it checks if it is a leaf node by checking if its left and right child nodes are null. If it is a leaf node, it checks if its value is equal to the sum of its left and right child nodes. If it is not a leaf node, it checks if it has any child nodes. If it does not have any child nodes, it is a leaf node and the result is true. Otherwise, the result is false.

The script then prints the result to stdout.

Note that this script assumes that the input is a valid binary tree, and that the values of the nodes are integers between -100 and 100. If the input is not a valid binary tree, or if the values of the nodes are not integers between -100 and 100, the script may produce incorrect results or crash.
🌐 Data from online sources 
def max_twin_sum(head):
    sum = 0
    max_sum = 0
    i = 0
    slow = head
    fast = head

    while fast and fast.next:
        fast = fast.next.next
        i += 1

    for j in range(i):
        sum = slow.val + fast.val
        max_sum = max(max_sum, sum)
        slow = slow.next
        fast = fast.prev

    return max_sum

The algorithm uses two pointers (slow and fast) to simultaneously traverse the linked list. The slow pointer moves forward one step at a time, while the fast pointer moves two steps at a time. This allows the fast_pointer to reach the end of the list when the slow_pointer is exactly halfway through the list.

After reaching the middle, the function iterates through the first half of the list, calculating the twin sum of each node with its twin (which is being referenced by the fast pointer) and storing the maximum value. To do this, it advances the slow pointer one step at a time, while the fast pointer moves one step back. At each step, it calculates the sum of the values at the current positions of the slow and fast pointers, updating the maximum twin sum if a higher sum is found.

Finally, after traversing half of the linked list, the function returns the maximum twin sum.

🌐 Data from online sources 
int maxTwinSum(ListNode* head) {
    int sum = 0, max_sum = 0, i = 0;
    ListNode* slow = head, *fast = head;

    while (fast && fast->next) {
        fast = fast->next->next;
        i++;
    }

    for (int j = 0; j < i; j++) {
        sum = slow->val + fast->val;
        max_sum = max(max_sum, sum);
        slow = slow->next;
        fast = fast->prev;
    }

    return max_sum;
}

The algorithm uses two pointers (slow and fast) to simultaneously traverse the linked list. The slow pointer moves forward one step at a time, while the fast pointer moves two steps at a time. This allows the fast_pointer to reach the end of the list when the slow_pointer is exactly halfway through the list.

After reaching the middle, the function iterates through the first half of the list, calculating the twin sum of each node with its twin (which is being referenced by the fast pointer) and storing the maximum value. To do this, it advances the slow pointer one step at a time, while the fast pointer moves one step back. At each step, it calculates the sum of the values at the current positions of the slow and fast pointers, updating the maximum twin sum if a higher sum is found.

Finally, after traversing half of the linked list, the function returns the maximum twin sum.