Question:

How to calculate Sum of leaf nodes in BST?

Summary:

Given a Binary Search Tree that contains n nodes, determine the total number of leaf nodes in the tree. The following is a property that BST possesses (it is possible to have duplicate nodes):

The left subtree of a node is comprised solely of nodes that have keys that are lower than the key of the node itself.

All of the nodes that are contained within the right subtree of a node have keys that are either greater than or equal to the key of the node.

In order to complete this task, you will need to calculate the total sum of the values of the leaf nodes.

Solution:

#User function Template for python3

##Structure of node

'''

class Node:

def __init__(self, data=0):

self.data=0

self.left=None

self.right=None

'''

class Solution:

def sumOfLeafNodes(self, root):

leafs_sum = 0

def dfs(node):

nonlocal leafs_sum

if node is None:

return

elif node.left is None and node.right is None:

leafs_sum += node.data

else:

dfs(node.left)

dfs(node.right)

dfs(root)

return leafs_sum

Explanation:

Function Signature:

The function sumOfLeafNodes is defined inside the Solution class. It takes root as a parameter, which is an instance of the Node class.

Initialization:

leafs_sum variable is initialized to 0. This variable will store the sum of leaf nodes' data.

Depth-First Search (DFS) Function (dfs):

This function is a nested function defined inside sumOfLeafNodes.
It takes a node as an argument.
It updates the leafs_sum variable by adding the data of leaf nodes encountered during the traversal.
It recursively explores the left and right subtrees of the current node until it reaches a leaf node (a node with no children).