0 like 0 dislike
793 views
| 793 views

0 like 0 dislike

Q1. Consider a binary tree of N nodes ( 1 Root and N-1 descendants). Each node X is related to root node by a relation such as L,R,LL,LR ... and so on. where X is left (L) to Root, or right to Root (R), or left-left (LL) or left-rigth (LR) to root and so on. Write a program to find the sum of all magic parents in the tree.

Magic parents are those nodes whose one child is a factor of the other child. The nodes having only one child can never be Magic parents.

Constraints:- 3<=N<=100

Input format:
The first line of input contains an Integer, N,The number of nodes in the tree.
The second line of input contains an integer , Root, which is the root of the tree.
The next N-1 lines of input contains a String ,and an integer X , separeted by a single white space, where X is a node in tree and S is the relation between Root and X.

Sample Input
6
11
L 14
R 28
LL 7
LR 8
RR 14

Sample Output
11

Based on the input , the tree can be constructed as follows :-

In the above tree only Magic parent is 11 as its children are 14 and 28,where 14 is factor of 28.
Hence output is 11.

by Expert (46,090 points)
0 like 0 dislike

Q1
O(n) Time and Space

``````#include<bits/stdc++.h>

using namespace std;

class Node {
public:
int value;
Node* left;
Node* right;

Node(int v = -1, Node* l = nullptr, Node* r = nullptr)
: value(v), left(l), right(r) {}
};

class BinaryTree {
public:
Node* root;

BinaryTree(int rv) { root = new Node(rv); }

void addNode(string relation, int val) {
Node* ptr = root;
int rl = relation.size();
for (int i = 0; i < rl - 1; i++) {
if (relation[i] == 'L')
ptr = ptr->left;
else
ptr = ptr->right;
}

if (relation.back() == 'L')
ptr->left = new Node(val);
else
ptr->right = new Node(val);
}
};

int sumOfMagicParents(Node* root) {
if (root == nullptr) return 0;

int sum = 0;
queue<Node*> q;
q.push(root);

while (!q.empty()) {
Node* curr = q.front();
q.pop();

if (curr->left != nullptr && curr->right != nullptr) {
// check if curr is magic parent
int leftVal = curr->left->value;
int rightVal = curr->right->value;

if (max(leftVal, rightVal) % min(leftVal, rightVal) == 0) {
sum += curr->value;
}
}

if (curr->left != nullptr) q.push(curr->left);
if (curr->right != nullptr) q.push(curr->right);
}

return sum;
}

int main() {
int n;  // number of nodes
cin >> n;
int rootVal;
cin >> rootVal;

BinaryTree bt(rootVal);

for (int i = 0; i < n - 1; i++) {
string rel;
int val;
cin >> rel >> val;