Flipkart Grid 8.0 | 18th July 2026 | Ladakh Marathon | Questions and Video Solutions | Kumar K

Question

Answer 1

/*Problem Statement:

 

You are given the number of nodes n and a list of n descriptions. The first description contains the value of the root node. Each subsequent description provides a path from the root to a specific node (using 'L' for left and 'R' for right) followed by the integer value of that node. Your task is to construct this binary tree and return the sum of the values of all nodes that have exactly two children.

 

Input Format:

 

n: An integer representing the total number of nodes.

paths: A list of strings/pairs. The first entry is [root_value]. Every other entry is a path string (e.g., "LRR") and the corresponding node value.

Example:

 

Input: n = 4, paths = ["24", "R 5", "L 10", "RRL 15"]

Output: (Sum of nodes with two children)

Constraints:

 

3 <= n <= 100

Paths are given as a series of 'L' (left) and 'R' (right) characters.

The tree structure is implicit; you must handle node creation as you traverse the paths.*/

 

#include <iostream>

#include <vector>

#include <string>

 

using namespace std;

 

struct Node{

Node* left;

Node* right;

int val;

 

Node(int x){

val = x;

left = right = NULL;

}

};

 

void AddLeft(Node* root,int x){

root->left = new Node(x);

}

 

void AddRight(Node* root,int x){

root->right = new Node(x);

}

 

int Sum(Node* root){

if(root == NULL) return 0;

 

int ans = 0;

 

if(root->left != NULL && root->right != NULL)

ans += root->val;

 

ans += Sum(root->left);

ans += Sum(root->right);

 

return ans;

}

 

int main(){

 

int N;

cin >> N;

 

int rVal;

cin >> rVal;

 

vector<pair<string,int>> Data;

 

for(int i = 1; i < N ; i++){

string s;

int value;

 

cin >> s >> value;

Data.push_back({s,value});

}

 

Node* root = new Node(rVal);

 

for(int i = 0; i < N - 1 ; i++){

 

string curs = Data[i].first;

int x = Data[i].second;

 

Node* temp = root;

 

int j = 0;

 

for(; j < (int)curs.size()-1 ; j++){

 

if(curs[j] == 'R'){

 

if(temp->right == NULL)

temp->right = new Node(0);

 

temp = temp->right;

}

else{

 

if(temp->left == NULL)

temp->left = new Node(0);

 

temp = temp->left;

}

}

 

if(curs[j] == 'R'){

 

if(temp->right == NULL)

AddRight(temp,x);

else

temp->right->val = x;

}

else{

 

if(temp->left == NULL)

AddLeft(temp,x);

else

temp->left->val = x;

}

}

 

cout << Sum(root) << endl;

 

return 0;

}