404 Sum of Left Leaves

Find the sum of all left leaves in a given binary tree.

Example:

    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 
9
 and 
15
 respectively. Return 
24
.

Complexity: O(N) time and space The Idea: Use any kind of traversal and keep track when you are on a left or right branch.

int sumOfLeftLeaves(TreeNode* root) {
    int sum = 0;
    preOrderLeftLeafAcc(root, sum, false);
    return sum;
}

void preOrderLeftLeafAcc(TreeNode* root, int &sum, bool isLeft) {
    if (root) {
        if (!root->left && !root->right && isLeft) {
            sum += root->val;
        }

        preOrderLeftLeafAcc(root->left, sum, true);
        preOrderLeftLeafAcc(root->right, sum, false);
    }
}

Last updated