JavaScript Program to Find Sum of Leaf Node in Binary Tree
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
Table of Content
- Using recursive approach
- Iterative Approach Using Stack
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));
Output
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));
Output
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.