Sum of Left Leaves

🏠 ⬅️ ➡️

Given the root of a binary tree, return the sum of all left leaves.

A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: 24 Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.

Example 2:

Input: root = [1] Output: 0

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • -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=20) :: filename
    type :: TreeNode
        real(kind=DP), pointer :: val => null()
        class(TreeNode), pointer :: left => null(), right => null()
    end type TreeNode
    type(TreeNode), pointer :: root
    integer :: i, n
    real(kind=DP) :: sum

    ! read input from file
    open(newunit=unit_in, file='input.txt', status='old', action='read')
    read(unit=unit_in, fmt=*) filename
    close(unit=unit_in)

    ! read data from file
    open(newunit=unit_in, file=filename, status='old', action='read')
    read(unit=unit_in, fmt=*) n
    allocate(root)
    call read_tree(unit_in, root)
    close(unit=unit_in)

    ! solve problem
    sum = sum_of_left_leaves(root)

    ! write output to file
    open(newunit=unit_out, file='output.txt', status='replace', action='write')
    write(unit=unit_out, fmt='(F0.2)') sum
    close(unit=unit_out)

contains

    subroutine read_tree(unit_in, root)
        integer, intent(in) :: unit_in
        class(TreeNode), pointer :: root
        integer :: i
        logical :: done

        done = .false.
        do while (.not. done)
            read(unit=unit_in, fmt=*, iostat=i)
            if (i /= 0) then
                done = .true.
            else
                allocate(root%left)
                call read_tree(unit_in, root%left)
                allocate(root%right)
                call read_tree(unit_in, root%right)
            end if
        end do
    end subroutine read_tree

    function sum_of_left_leaves(root) result(sum)
        class(TreeNode), pointer :: root
        real(kind=DP) :: sum
        integer :: i

        if (associated(root)) then
            if (associated(root%left)) then
                if (.not. associated(root%left%left) .and. &
                    .not. associated(root%left%right)) then
                    sum = sum + root%left%val
                else
                    sum = sum + sum_of_left_leaves(root%left)
                end if
            end if
            sum = sum + sum_of_left_leaves(root%right)
        end if
    end function sum_of_left_leaves

end program main
❌ Compiled
❌ Executed
❌ Correct 
module BinaryTree

    implicit none

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

    interface
        function sum_of_left_leaves(root) result(sum)
            type(Node), pointer, intent(in) :: root
            integer :: sum
        end function sum_of_left_leaves
    end interface

end module BinaryTree

program main
    use BinaryTree
    implicit none
    type(Node), pointer :: root
    integer :: sum

    ! Example 1
    root => Node(val=3, left=Node(val=9, left=Node(val=15, left=Node(val=7), right=Node(val=20)), right=Node(val=20)), right=Node(val=15, left=Node(val=7), right=Node(val=20)))
    sum = sum_of_left_leaves(root)
    write (*,*) "Example 1: Sum of left leaves = ", sum

    ! Example 2
    root => Node(val=1, left=Node(val=2, left=Node(val=3), right=Node(val=4)), right=Node(val=2, left=Node(val=3), right=Node(val=4)))
    sum = sum_of_left_leaves(root)
    write (*,*) "Example 2: Sum of left leaves = ", sum

contains

    function sum_of_left_leaves(root) result(sum)
        type(Node), pointer, intent(in) :: root
        integer :: sum
        type(Node), pointer :: current

        sum = 0
        current => root

        do while (associated(current))
            if (associated(current%left)) then
                if (associated(current%left%left) .and. .not. associated(current%left%right)) then
                    sum = sum + current%left%val
                end if
            end if
            current => current%right
        end do

    end function sum_of_left_leaves

end program main
🌐 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 sum_of_left_leaves(root):
    if not root:
        return 0
    left_sum = 0
    if root.left and not root.left.left and not root.left.right:
        left_sum += root.left.val
    return left_sum + sum_of_left_leaves(root.left) + sum_of_left_leaves(root.right)

The algorithm uses a recursive approach. For every node in the tree, the program checks if the left child is a leaf node by verifying if it exists and if it has no children. If the left child is a leaf, add its value to the sum, and then call the function for both left and right children of the current node. Since the tree can have varying depths, recursion is useful to explore each subtree and accumulate the sum of all left leaves.

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

int sumOfLeftLeaves(TreeNode* root) {
    if (!root) return 0;
    int sum = 0;
    if (root->left && !root->left->left && !root->left->right) sum += root->left->val;
    return sum + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
}

The algorithm uses a recursive approach. For every node in the tree, the program checks if the left child is a leaf node by verifying if it exists and if it has no children. If the left child is a leaf, add its value to the sum, and then call the function for both left and right children of the current node. Since the tree can have varying depths, recursion is useful to explore each subtree and accumulate the sum of all left leaves.