PROBLEM OF THE DAY : 18/02/2024 | Sum of leaf nodes in BST

Welcome to the daily solving of our PROBLEM OF THE DAY with Karan Mashru. We will discuss the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up on your concepts of BST but also build up problem-solving skills.

In this problem, we are 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 :

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

Give the problem a try before going through the video. All the best!!!
Problem Link: https://www.geeksforgeeks.org/problems/sum-of-leaf-nodes-in-bst/1