Binary Tree Tilt

🏠 ⬅️ ➡️

Given the root of a binary tree, return the sum of every tree node's tilt.

The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values. If a node does not have a left child, then the sum of the left subtree node values is treated as 0. The rule is similar if the node does not have a right child.

Example 1:

Input: root = [1,2,3] Output: 1 Explanation: Tilt of node 2 : |0-0| = 0 (no children) Tilt of node 3 : |0-0| = 0 (no children) Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3) Sum of every tilt : 0 + 0 + 1 = 1

Example 2:

Input: root = [4,2,9,3,5,null,7] Output: 15 Explanation: Tilt of node 3 : |0-0| = 0 (no children) Tilt of node 5 : |0-0| = 0 (no children) Tilt of node 7 : |0-0| = 0 (no children) Tilt of node 2 : |3-5| = 2 (left subtree is just left child, so sum is 3; right subtree is just right child, so sum is 5) Tilt of node 9 : |0-7| = 7 (no left child, so sum is 0; right subtree is just right child, so sum is 7) Tilt of node 4 : |(3+5+2)-(9+7)| = |10-16| = 6 (left subtree values are 3, 5, and 2, which sums to 10; right subtree values are 9 and 7, which sums to 16) Sum of every tilt : 0 + 0 + 0 + 2 + 7 + 6 = 15

Example 3:

Input: root = [21,7,14,1,1,2,2,3,3] Output: 9

Constraints:

  • The number of nodes in the tree is in the range [0, 104].
  • -1000 <= Node.val <= 1000
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, DP => REAL64
    implicit none
    integer, parameter :: unit_in = 10, unit_out = 20
    character(len=*), parameter :: filename_in = "example_input.txt"
    character(len=*), parameter :: filename_out = "example_output.txt"
    type :: node_type
        real(kind=DP) :: val
        type(node_type), pointer :: left, right
    end type node_type
    type(node_type), pointer :: root
    integer :: i, n
    real(kind=DP) :: tilt

    ! Read input from file
    open(newunit=unit_in, file=filename_in, status='old', action='read')
    read(unit=unit_in, fmt=*) n
    allocate(root)
    do i = 1, n
        read(unit=unit_in, fmt=*) root%val
        call solve(root)
    end do
    close(unit=unit_in)

    ! Write output to file
    open(newunit=unit_out, file=filename_out, status='replace', action='write')
    write(unit=unit_out, fmt=*) tilt
    close(unit=unit_out)

contains

    recursive subroutine solve(this)
        class(node_type), intent(inout) :: this
        if (.not. associated(this)) return
        call solve(this%left)
        call solve(this%right)
        tilt = abs(sum(this%left%val) - sum(this%right%val))
    end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module tilt

implicit none

contains

function tilt_sum(root) result(sum)

! Given the root of a binary tree, return the sum of every tree node's tilt.
! The tilt of a tree node is the absolute difference between the sum of all left subtree node values and all right subtree node values.
! If a node does not have a left child, then the sum of the left subtree node values is treated as 0. The rule is similar if the node does not have a right child.

type(node), pointer, intent(in) :: root
integer :: sum

sum = tilt_sum_helper(root)

end function tilt_sum

recursive function tilt_sum_helper(node) result(sum)

! Helper function to calculate the tilt sum of a node and its children.

type(node), pointer, intent(in) :: node
integer :: sum

if (associated(node)) then
    sum = abs(tilt_sum_helper(node%left) - tilt_sum_helper(node%right))
    if (associated(node%left)) sum = sum + tilt_sum_helper(node%left)
    if (associated(node%right)) sum = sum + tilt_sum_helper(node%right)
else
    sum = 0
endif

end function tilt_sum_helper

end module tilt

! Test cases
program test

use tilt
implicit none

! Test case 1
type(node), pointer :: root
integer :: sum

root => node(1, node(2, node(3), node(4)), node(5))
sum = tilt_sum(root)
write (*,*) "Tilt sum of the tree:", sum

! Test case 2
root => node(4, node(2, node(3), node(5)), node(7))
sum = tilt_sum(root)
write (*,*) "Tilt sum of the tree:", sum

! Test case 3
root => node(21, node(7), node(14, node(1), node(1, node(2), node(2)), node(3, node(3))), node(2, node(2)))
sum = tilt_sum(root)
write (*,*) "Tilt sum of the tree:", sum

end program test

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

contains

! Constructor
type(node) function node(val, left, right)

integer, intent(in) :: val
type(node), pointer, optional :: left
type(node), pointer, optional :: right

node%val = val
if (present(left)) then
    node%left => left
else
    nullify(node%left)
endif
if (present(right)) then
    node%right => right
else
    nullify(node%right)
endif

end function node

end type node
🌐 Data from online sources 
def findTilt(self, root):
    def findTiltUtil(node):
        if not node: return 0, 0

        leftSum, leftTilt = findTiltUtil(node.left)
        rightSum, rightTilt = findTiltUtil(node.right)

        return (node.val + leftSum + rightSum, abs(leftSum - rightSum) + leftTilt + rightTilt)

    return findTiltUtil(root)[1]

The problem can be solved using a bottom-uprecursive algorithm. The helper function `findTiltUtil` should return two values: the sum of the current node and its descendants and the tilt value of the current node and its descendants.

The base case is when the current node is null, in this case, return [0, 0].

If the current node is not null, recursively call the findTiltUtil for left and right children. Then add the sum of the left child and the right child's sum, plus the value of the current node to get the new sum. For the new tilt value, add the absolute difference between the left and right child's sum to the tilt value of both children.

Finally, return the new sum and tilt value as a tuple or a list. When calling this helper function for the root, the tilt value of the whole tree will be in the second element of the result list.

🌐 Data from online sources 
int findTiltUtil(TreeNode* root, int& tiltSum) {
    if (!root) return 0;

    int leftSum = findTiltUtil(root->left, tiltSum);
    int rightSum = findTiltUtil(root->right, tiltSum);

    tiltSum += abs(leftSum - rightSum);
    return root->val + leftSum + rightSum;
}

int findTilt(TreeNode* root) {
    int tiltSum = 0;
    findTiltUtil(root, tiltSum);
    return tiltSum;
}

The problem can be solved using a bottom-uprecursive algorithm. The helper function `findTiltUtil` should return two values: the sum of the current node and its descendants and the tilt value of the current node and its descendants.

The base case is when the current node is null, in this case, return [0, 0].

If the current node is not null, recursively call the findTiltUtil for left and right children. Then add the sum of the left child and the right child's sum, plus the value of the current node to get the new sum. For the new tilt value, add the absolute difference between the left and right child's sum to the tilt value of both children.

Finally, return the new sum and tilt value as a tuple or a list. When calling this helper function for the root, the tilt value of the whole tree will be in the second element of the result list.