[Solved] Alternate Leaf Nodes Sum Contest Problem

Alternate Leaf Nodes Sum: You need to build a BST from the given array A of size N. The array contains distinct elements. You need to build the tree using the Array elements in the order of their arrival (A[0] becomes root and so on). Now, you need to sum the alternate leaf nodes of this BST and print the result.
Note: Start from the left side of the tree when searching for leaf nodes. So sum leaftnode1+leaftnode3+leafnode5 …

Input:
The first line of input contains T denoting the number of testcases. T testcases follow. Each testcase contains two lines of input. The first line contains N. The second line contains array elements.

Output:
For each testcase, in a new line, print the sum of alternate leaf nodes.

Constraints:
1 <= T <= 200
1 <= N <= 10⁷
1 <= A_i <= 10⁸

Examples:
Input:
1
6
5 1 2 3 4 6
Output:
4

Explanation:
Testcase1:
The BST will look like :
            5
          /     \
        1        6
         \         
            2                
               \          
                3  
                    \
                        4
As it is evident from the above BST, the leaf nodes are 4 and 6. So sum of alternate leaf nodes would be 4.

Solution

#include <bits/stdc++.h>
using namespace std;

vector<int>v;

struct Node{
  
  int data;
  Node *left;
  Node *right;
  
};

Node *newNode(int key)
{
    Node *temp=new Node;
    temp->data=key;
    temp->left=NULL;
    temp->right=NULL;
    return temp;
}

Node *insertNode(Node *head,int key)
{
    if(head==NULL)
    head=newNode(key);
    else
    {
        if(key<=head->data)
        head->left=insertNode(head->left,key);
        else
        head->right=insertNode(head->right,key);
    }
    return head;
}

void leafSumAlternate(Node *head)
{
  
    if(head==NULL)
        return;
    if(head->left==NULL&&head->right==NULL)
    { 
        v.push_back(head->data);
        return;
        
    }
     leafSumAlternate(head->left);
     leafSumAlternate(head->right);
     return;
}

void sumAlternate()
{
    int sum=0;
     for(int i=0;i<v.size();i=i+2)
     {
         sum+=v[i];
     }
     cout<<sum<<endl;
}

int main() {
	
	int t;
	cin>>t;
	while(t--)
	{
	    v.clear();
	    Node *root=NULL;
	    int n;
	    cin>>n;

//sauravhathi
	    for(int i=0;i<n;i++)
	    {
	        int x;
	        cin>>x;
	        root=insertNode(root,x);
	    }
	  
	    leafSumAlternate(root);
	    sumAlternate();
	    
	}
	return 0;
}

import java.io.*;
import java.lang.*;
import java.util.*;

class Node {
    int data;
    Node left, right;
    Node(int key){
        this.data = key;
        this.left = this.right = null;
    }
}

class GfG { 
    
    static ArrayList<Integer> leafs;
    
    static Node insertInBST(Node root, int key) { 
        if (root == null) return new Node(key); 
	    if (key < root.data) root.left = insertInBST(root.left, key); 
	    else root.right = insertInBST(root.right, key); 
	    return root; 
    }
    
    static void bstLeafS(Node head) {
        if (head == null) {
            return;
        }
        if(head.left == null && head.right == null){
            leafs.add(head.data);
            return;
        }
        bstLeafS(head.left);
        bstLeafS(head.right);
        return;
    }
    
    static int alternateLeafSum(Node head) {
        bstLeafS(head);
        int res=0;
        for(int i=0; i<leafs.size(); i=i+2)res+=leafs.get(i);
        return res;
    }
    
    public static void main (String[] args) throws IOException  {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine().trim());
		while(t-->0){
		    String inputLine[] = br.readLine().trim().split(" ");
		    int n = Integer.parseInt(inputLine[0]);
		    Node root = null;
		    inputLine = br.readLine().trim().split(" ");
		    root = insertInBST(root, Integer.parseInt(inputLine[0]));
		    for(int i=1; i<n; i++){
		        insertInBST(root, Integer.parseInt(inputLine[i]));
		    }
		    leafs = new ArrayList<>();
		    System.out.println(alternateLeafSum(root));
		}
	}
} 

Happy Learning – If you require any further information, feel free to contact me.