Horje
Find the Sum of All Left Leaves in a Given Binary Tree using JavaScript

Given a Binary Tree, find the sum of all left leaves in it. A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. Finding the sum of all left leaves involves traversing the entire binary tree and checking each node to determine whether it qualifies as a left leaf.

Leaf Node: Leaf Nodes are the nodes in the tree which have no child or we can say both left and right pointers are NULL.

Example:

Input:
                                                                9
                                                            /       \
                                                          8           6
                                                        /   \         /  
                                                     5       2      1
Output: 5+1=6

Recursive Approach

The Approach is to traverse the tree from root and for every node check if its left node is leaf or not. If the left node is leaf node then add it to the sum.

The leftLeavesSum function initializes a sum accumulator and traverses the tree, adding values from left leaf nodes to the accumulator. It recursively explores each node’s left and right subtrees to accumulate sums of left leaf nodes. The function returns the total sum of all identified left leaf node values in the binary tree, leveraging recursive traversal to ensure comprehensive coverage of the tree’s structure and content.

Example: The example below shows the implementation.

JavaScript
class Node {
    constructor(k) {
        this.data = k;
        this.left = null;
        this.right = null;
    }

}

function isLeaf(node) {
    if (node == null)
        return false;
    if (node.left == null && node.right == null)
        return true;
    return false;
}

// This function returns sum of all left 
// leaves in a given binary tree
function leftLeavesSum(node) {

    // Initialize result
    let res = 0;

    // Update result if root is not NULL
    if (node != null) {

        // If left of root is NULL, then add key of
        // left child
        if (isLeaf(node.left))
            res += node.left.data;
        else // Else recur for left child of root
            res += leftLeavesSum(node.left);

        // Recur for right child of root and update res
        res += leftLeavesSum(node.right);
    }

    // return result
    return res;
}

root = new Node(20);
root.left = new Node(9);
root.right = new Node(49);
root.left.right = new Node(12);
root.left.left = new Node(5);
root.right.left = new Node(23);
root.right.right = new Node(52);
root.left.right.right = new Node(12);
root.right.right.left = new Node(50);

console.log("The sum of leaves is " + leftLeavesSum(root));

Output
The sum of leaves is 78

Time Complexity: O(N) where N is the number of nodes in given binary tree.

Auxiliary Space: O(h) where h is the height of given binary tree.

Iterative Approach

This approach involves Depth-First Traversal on the tree (either Inorder, Preorder or Postorder) using a stack and checking if the Left Child is a Leaf node. If it is, then add the nodes value to the sum.

The method initializes a stack and pushes the root node onto it. It iteratively processes nodes from the stack, checking if each node’s left child is a leaf (both left and right children are null). If a left leaf node is found, its key value is added to the sum. Nodes are processed in a depth-first manner by pushing right children onto the stack after processing left children. Finally, the function returns the computed sum of all identified left leaf nodes in the binary tree.

Example: The example below shows the implementation.

JavaScript
// JavaScript program to find sum of all left leaves
// A binary tree node
class Node {

    // A constructor to create a new Node
    constructor(key_) {
        this.key = key_;
        this.left = null;
        this.right = null;
    }
};
// Return the sum of left leaf nodes
function sumOfLeftLeaves(root) {
    if (root == null)
        return 0;
    // Using a stack_ for Depth-First 
    // Traversal of the tree
    let stack_ = [];
    stack_.push(root);
    // sum holds the sum of all the left leaves
    let sum = 0;
    while (stack_.length > 0) {
        let currentNode = stack_[stack_.length - 1];
        stack_.pop();
        if (currentNode.left != null) {
            stack_.push(currentNode.left);
            // Check if currentNode's left 
            // child is a leaf node
            if (currentNode.left.left == null &&
                currentNode.left.right == null) {
                // if currentNode is a leaf, 
                // add its data to the sum 
                sum = sum + currentNode.left.key;
            }
        }
        if (currentNode.right != null)
            stack_.push(currentNode.right);
    }
    return sum;
}

let root = new Node(20);
root.left = new Node(9);
root.right = new Node(49);
root.right.left = new Node(23);
root.right.right = new Node(52);
root.right.right.left = new Node(50);
root.left.left = new Node(5);
root.left.right = new Node(12);
root.left.right.right = new Node(12);
console.log("Sum of left leaves is "
    + sumOfLeftLeaves(root));

Output
Sum of left leaves is 78

Time Complexity: O(N) where N is the number of nodes in given binary tree.

Auxiliary Space: O(h) where h is the height of given binary tree.




Reffered: https://www.geeksforgeeks.org


JavaScript

Related
Polyfill for Array.prototype.filter Method in JavaScript Polyfill for Array.prototype.filter Method in JavaScript
How to Fix "Invalid Shorthand Property Initializer" in JavaScript? How to Fix "Invalid Shorthand Property Initializer" in JavaScript?
Difference Between Sums of Odd Level and Even Level Nodes of a Binary Tree using JavaScript Difference Between Sums of Odd Level and Even Level Nodes of a Binary Tree using JavaScript
Difference Between Array.prototype.map() and Array.prototype.flatMap() in JavaScript Difference Between Array.prototype.map() and Array.prototype.flatMap() in JavaScript
JavaScript Program for Rightmost and Leftmost Node of a Binary Tree JavaScript Program for Rightmost and Leftmost Node of a Binary Tree

Type:
Geek
Category:
Coding
Sub Category:
Tutorial
Uploaded by:
Admin
Views:
17