Sum of Left Leaves

Problem statement

Given the root of a binary tree, return the sum of all left leaves. A left leaf is a node that is the left child of its parent and has no children of its own.

Example:

Input:

root = [3, 9, 20, null, null, 15, 7]

Expected output:

24

Why: 9 is a left leaf; 15 is a left leaf of 20. 9 + 15 = 24.

Practice on LeetCode: Sum of Left Leaves

Golang Solution

At each node, if the left child exists and is a leaf, take its value; otherwise recurse into the left subtree. Always recurse on the right (right-side leaves are never added as “left” leaves).

Time: O(n)
Space: O(h) recursion stack

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumOfLeftLeaves(root *TreeNode) int {
    if root == nil {
        return 0
    }

    var left, right int
    if root.Left != nil {
        if root.Left.Left == nil && root.Left.Right == nil {
            left = root.Left.Val
        } else {
            left = sumOfLeftLeaves(root.Left)
        }
    }

    right = sumOfLeftLeaves(root.Right)

    return left + right
}