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.
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