Problem Link : Sum of leaf nodes in BST [GeeksforGeeks]
Problem Description : Sum of leaf nodes in BST
Given a Binary Search Tree with n nodes, find the sum of all leaf nodes. BST has the following property (duplicate nodes are possible):
- The left subtree of a node contains only nodes with keys less than the node’s key.
- The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Your task is to determine the total sum of the values of the leaf nodes.
Note: Input array arr doesn’t represent the actual BST, it represents the order in which the elements will be added into the BST.
Example 1:
Input:
n = 6
arr = {67, 34, 82, 12, 45, 78}
Output:
135
Explanation:
In first test case, the BST for the given input will be-
67
/ \
34 82
/ \ /
12 45 78
Hence, the required sum= 12 + 45 + 78 = 135
Example 2:
Input:
n = 1
arr = {45}
Output:
45
Explanation:
As the root node is a leaf node itself, the required sum will be 45
Your Task:
You don’t have to take any input or print anything. You are required to complete the function sumOfLeafNodes that takes root node of a BST with n nodes as parameter and returns the sum of leaf nodes.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
1 <= n <= 104
1 <= Value of each node <= 105
Solution :
Algorithm to Find Sum of Leaf Nodes in a Binary Tree:
Initialize a Variable: Begin by initializing a variable (e.g.,
soln) to store the sum of leaf nodes. Set it to zero.Define a Recursive Function: Create a recursive function (e.g.,
sumOfLeafNodes) that takes a node as an argument.Base Case: In the recursive function, check if the current node is null. If so, return 0.
Leaf Node Check: Check if the current node is a leaf node (both left and right children are null). If it is, return the data of the current node.
Recursive Calls: Make recursive calls to the
sumOfLeafNodesfunction for the left and right children of the current node.Traverse the Tree: Start the traversal by calling
sumOfLeafNodeswith the root of the binary tree.Return the Result: Return the final value of the
solnvariable as the sum of leaf nodes.
Code :
class Solution
{
public static int sumOfLeafNodes(Node root)
{
if(root == null){
return 0;
}
if(root.left == null && root.right == null){
return root.data;
}
return sumOfLeafNodes(root.left) + sumOfLeafNodes(root.right);
}
}
int sumOfLeafNodes(Node* root) {
if (root == nullptr)
return 0;
if (root->left == nullptr && root->right == nullptr)
return root->data;
return sumOfLeafNodes(root->left) + sumOfLeafNodes(root->right);
}
class Solution:
def sumOfLeafNodes(self, root):
def dfs(node):
nonlocal soln
if not node:
return
if not node.left and not node.right:
soln += node.data
dfs(node.left)
dfs(node.right)
soln = 0
dfs(root)
return soln
Output :
Output: 135
Also Read : Does array represent Heap
