Sum of Left Leaves

Problem:

Given the root of a binary tree, return the sum of all left leaves. Left leaf is a leaf node which has no children and is the left child of another node.

Algorithm:

1. Traverse the binary tree and perform the following operations;
   1. During the traversal, use a flag isLeftNode to identify left nodes.
   2. Add the value of a left child node to the sum if it is a leaf node (i.e., it has no child nodes).
2. After completing the traversal, return the total sum of all leaf left nodes.

This algorithm traverses the binary tree, checking each left child node. If the left child is a leaf (no children), its value is added to the total sum. The sum of all such leaf left nodes is then returned.

Solution & Visualize:

The animation/visualization below demonstrates how the algorithm works.

function calculateSum(root, sum, isLeftNode) {
    if (root === null) return sum;

    if (isLeftNode && root.left === null && root.right === null) {
        sum += root.data;
        return sum;
    }

    sum = calculateSum(root.left, sum, 1);
    sum = calculateSum(root.right, sum, 0);

    return sum;
}

const nodes = [1, 2, 3, 4, 5, null, null, null, null, 10];
const root = buildTree(nodes);

calculateSum(root, 0, 0); // 14
                                        

class TreeNode {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

function buildTree(nodes, index, size) {
    if (index < size) {
        if (nodes[index] === null) {
            return null;
        }

        let root = new TreeNode(nodes[index]);
        root.left = buildTree(nodes, 2 * index + 1, size);
        root.right = buildTree(nodes, 2 * index + 2, size);

        return root;
    }

    return null;
}