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 ApproachThe 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));
OutputThe 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 ApproachThis 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));
OutputSum 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.
|