Given a binary tree, We have to find the sum of all leaf nodes. A leaf node is a node that does not have any children.

Example:

Input binary tree:
        1
       / \
      2   3
     / \ / \
    4  5 6  7
The sum of leaf nodes would be: 4 + 5 + 6 + 7 = 22

Using recursive approach

In this approach, we define a recursive function sumOfLeafNodesRecursive that traverses the binary tree recursively. It calculates the sum of leaf nodes by recursively summing leaf node values starting from a given node. If the input node is a leaf node, its value is returned; otherwise, the function recursively calculates the sum of leaf nodes for its left and right children.

Approach:

• Initialize a variable sum to store the sum of leaf nodes.
• Define a recursive function that takes a node as input.
• If the node is null, return.
• If the node is a leaf node (i.e., it has no left or right child), add its value to the sum.
• Recursively call the function for the left and right children of the node.
• Return the sum.

Example: This example uses recursive approach to calculates the sum of leaf node in binary tree.

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

function sumOfLeafNodes(root) {
    if (!root) return 0;

    if (root.left === null && root.right === null) {
        return root.value;
    }

    return sumOfLeafNodes(root.left) +
        sumOfLeafNodes(root.right);
}

// Constructing the binary tree
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

console.log(sumOfLeafNodes(root));

12

Time complexity: O(n), where h is the height of the tree.

Space complexity: O(h), where n is the number of nodes in the tree.

Iterative Approach Using Stack

This approach employs an iterative depth-first traversal of the binary tree using a stack. Starting with the root node, it iterates while there are nodes in the stack. At each iteration, it pops a node from the stack and checks if it is a leaf node. If it is, its value is added to the sum. If it’s not a leaf node, its children are pushed onto the stack.

Approach:

• Initialize a stack with the root node.
• Iterate through the stack while it’s not empty.
• Pop a node from the stack.
• If it’s a leaf node, add its value to the sum.
• If it’s not a leaf node, push its children onto the stack.

Example: This example uses Iterative approach to calculates the sum of leaf node in binary tree.

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

function sumLeafs(root) {
    if (!root) return 0;

    let s = 0;
    let q = [root];

    while (q.length) {
        let n = q.pop();

        if (n.left === null && n.right === null) {
            s += n.value;
        } else {
            if (n.right) q.push(n.right);
            if (n.left) q.push(n.left);
        }
    }

    return s;
}

// Constructing the binary tree
let r = new Node(1);
r.left = new Node(2);
r.right = new Node(3);
r.left.left = new Node(4);
r.left.right = new Node(5);

console.log(sumLeafs(r));

12

Time complexity: O(n), where h is the height of the tree.

Space complexity: O(h), where n is the number of nodes in the tree.