Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Plagiarism Test

Last Updated on March 30, 2022 by Ria Pathak

BFS , Recursion

Easy

### Problem Statement :

Given a binary tree, and a node `X`, we have to sum all the nodes except the node `X`.
See example in the link given below.

See original problem statement here

#### Introduction :

Idea is to traverse all the nodes except `X` and add the values of the nodes to the answer.
We can any traversal method to perform this operations.

#### Method 1 (using Queue):

We can use a queue to perform level order traversal. We will perform following operations :

1. Create an empty queue q and a counter to store the size.
2. push the root node into the queue `(q.push(root))` and do following while `q` is not empty:
• pop the front element of queue (`temp=q.front()`).
• if `temp->left` & `temp->right` is not NULL, push them into the `q`.
• add the value of temp to answer `(answer += temp->value)`.

#### Method 2 (Recursion) :

Introduction says it all, all we need is to sum up the values left node & right node recursively and discard the node when it is `X`.
We will do the same for left & right subtrees by recursively calling , `root->left` & `root->right`.

### SOLUTIONS:

```#include <stdio.h>
#include<stdlib.h>
#define ll long long
#define REP(i, n) for (i = 0; i < n; i++)

struct nodelist
{
int value;
struct nodelist *left;
struct nodelist *right;
};
typedef struct nodelist node;
struct Queue
{
int front, rear, size;
unsigned capacity;
node* *array;
};
typedef struct Queue queue;

queue* createQueue(unsigned capacity)
{
queue* qu =(queue*)malloc(sizeof(queue));
qu->capacity = capacity;
qu->front = qu->size =0;
qu->rear = capacity-1;
qu->array = (node **)malloc(qu->capacity * sizeof(node));
return qu;
}

int isFull(queue*  queue1)
{
return (queue1->size == queue1->capacity);
}
int isEmpty(queue* queue1)
{
return (queue1->size==0);
}

void enqueue(queue* queue1, node* item)
{
if(isFull(queue1))
return ;
queue1->rear = (queue1->rear +1 )%queue1->capacity;
queue1->array[queue1->rear] = item;
queue1->size = queue1->size +1;

}

node dequeue(queue* queue1)
{
node* item = queue1->array[queue1->front];
queue1->front = (queue1->front +1)%queue1->capacity;
queue1->size = queue1->size -1;
return *item;
}

node* front(queue* queue1)
{
return queue1->array[queue1->front];
}

node* rear(queue * queue1)
{
return queue1->array[queue1->rear];
}
node *createNode(int value)
{
node *t= (node *) malloc(sizeof(node));
t->value = value;
t->right = t->left = NULL;
return  t;
}
void deleteNode(node*t)
{
free(t);
}

node *replaceNegativeOne(node *root)
{
if(root==NULL ||(root->value == -1 && root->left == NULL && root->right == NULL))
return NULL;
root->left = replaceNegativeOne(root->left);
root->right = replaceNegativeOne(root->right);
return root;
}

void deleteTree(node *node1)
{
if(node1==NULL)
return;
deleteTree(node1->left);
deleteTree(node1->right);
free(node1);
}
void inOrderTraversal(node *t)
{
//write your code here;
if (t == NULL)
return;

inOrderTraversal(t->left);
printf("%d ",t->value);
inOrderTraversal(t->right);
}
node *createTreeByLevelTree()
{
int n,m;
queue* queue1 = createQueue(100000);
node *root, *t;
root = NULL;
while(scanf("%d", &n))
{
if(isEmpty(queue1))
{
root= createNode(n);
enqueue(queue1,root);
continue;
}
scanf("%d", &m);
t = front(queue1);
dequeue(queue1);
t->left =createNode(n);
t->right=createNode(m);
if(t->left->value !=-1)
enqueue(queue1,t->left);
if(t->right->value !=-1)
enqueue(queue1,t->right);

if(isEmpty(queue1))
break;
}
return root;
}

int PlagiarismTest(struct nodelist *root,int x)
{
// write your code here
if(root == NULL) {
return 0;
}

if(root->value==x)
return 0;

if(!root->left && !root->right)
return root->value;

int l= PlagiarismTest(root->left,x);
int r=PlagiarismTest(root->right, x);

return l + r + root->value ;
}

int main() {

struct nodelist *root = NULL;
int x;
scanf("%d", &x);
root = createTreeByLevelTree();
root = replaceNegativeOne(root);

int ans=PlagiarismTest(root,x);
printf("%d",ans);
return 0;

}
```
```#define REP(i, n) for (i = 0; i < n; i++)

#define pb(a) push_back(a)

#define vi vector<long>

#define ll long long

#include <bits/stdc++.h>

using namespace std;

struct node

{

int value;

node *left;

node *right;

};

node *createNode(int value)

{

node *t = new node();

t->value = value;

t->right = t->left = NULL;

return t;

}
void deleteNode(node *t)
{

delete t;

}

void inorder(node *t)

{

if (t == NULL)

return;

inorder(t->left);

cout << t->value << " ";

inorder(t->right);

}

node *replaceNegativeOne(node *root)

{

if (root == nullptr || (root->value == -1 && root->left == nullptr && root->right == nullptr))

return nullptr;

root->left = replaceNegativeOne(root->left);

root->right = replaceNegativeOne(root->right);

return root;

}

node *createTreeByLevelTree()

{
int n, m;
queue<node *> q;
node *root, *t;
root = nullptr;

while (cin >> n)

{

if (q.empty())

{

root = createNode(n);

q.push(root);
continue;
}
cin >> m;
t = q.front();

q.pop();

t->left = createNode(n);

t->right = createNode(m);

if (t->left->value != -1)

{

q.push(t->left);

}

if (t->right->value != -1)

{

q.push(t->right);

}

if (q.empty())

{
break;
}
}
return root;

}

void deleteTree(node *node)

{

if (node == nullptr)

return;

deleteTree(node->left);

deleteTree(node->right);

delete node;

}

int PlagiarismTest(struct node *root, int x) {
if(root==NULL || root->value == x)
return 0;
return root->value + PlagiarismTest(root->left,x) + PlagiarismTest(root->right,x);
}

int main()
{
node *root = nullptr;
int x;
cin>>x;
root = createTreeByLevelTree();
root = replaceNegativeOne(root);
int ans=PlagiarismTest(root, x);
cout<<ans;
return 0;
}
```
```import java.util.*;
import java.io.*;

class Node
{
int value;
Node left, right;

public Node(int item)
{
value = item;
left = right = null;
}
}
class BinaryTree {
Node root;

BinaryTree() {
root = null;
}

Node createNode(int value) {
Node t = new Node(value);
return t;
}

Node replaceNegativeOne(Node root) {
if (root == null || (root.value == -1 && root.left == null && root.right == null)) {
return null;
}
root.left = replaceNegativeOne(root.left);
root.right = replaceNegativeOne(root.right);
return root;
}

Node createTreeByLevelTree(Scanner sc) {

int n, m;
Node t;
root = null;
while (sc.hasNext()) {
n = sc.nextInt();
if (queue.isEmpty()) {
root = createNode(n);
continue;
}
m = sc.nextInt();
t = queue.peekFirst();
queue.pop();
t.left = createNode(n);
t.right = createNode(m);
if (t.left.value != -1)
if (t.right.value != -1)
if (queue.isEmpty()){
break;
}
}
return root;
}
void deleteTree(Node node) {
node = null;
}

static void inOrderTraversal(Node node) {

//write your code here
if(node == null)
return;
inOrderTraversal(node.left);
System.out.print(node.value+" ");
inOrderTraversal(node.right);
}

int PlagiarismTest(Node root, int x)
{
// write your code here
if(root == null) {
return 0;
}

if(root.value==x)
return 0;

if(root.left ==null && root.right == null)
return root.value;

int l= PlagiarismTest(root.left,x);
int r=PlagiarismTest(root.right, x);

return l + r + root.value ;
}
}
public class Main {
public static void main(String[] args) {
// write your code here
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
BinaryTree bt = new BinaryTree();
bt.root = bt.createTreeByLevelTree(sc);
bt.root = bt.replaceNegativeOne(bt.root);

int ans=bt.PlagiarismTest(bt.root,x);
System.out.println(ans);

bt.deleteTree(bt.root);
}
}
```

[forminator_quiz id="2385"]
This article tried to discuss the concept of BFS , Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on BFS , Recursion you can check out MYCODE | Competitive Programming.