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!
Trees Interview Questions

Plagiarism Test

Harsh

Last Updated on March 30, 2022 by Ria Pathak

Concepts Used

BFS , Recursion

Difficulty Level

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

Solution Approach :

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).
  3. Return answer.

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:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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;

}
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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;
}
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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;
LinkedList<Node> queue = new LinkedList<>();
Node t;
root = null;
while (sc.hasNext()) {
n = sc.nextInt();
if (queue.isEmpty()) {
root = createNode(n);
queue.add(root);
continue;
}
m = sc.nextInt();
t = queue.peekFirst();
queue.pop();
t.left = createNode(n);
t.right = createNode(m);
if (t.left.value != -1)
queue.add(t.left);
if (t.right.value != -1)
queue.add(t.right);
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);
}
}
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; LinkedList<Node> queue = new LinkedList<>(); Node t; root = null; while (sc.hasNext()) { n = sc.nextInt(); if (queue.isEmpty()) { root = createNode(n); queue.add(root); continue; } m = sc.nextInt(); t = queue.peekFirst(); queue.pop(); t.left = createNode(n); t.right = createNode(m); if (t.left.value != -1) queue.add(t.left); if (t.right.value != -1) queue.add(t.right); 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); } }
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;
        LinkedList<Node> queue = new LinkedList<>();
        Node t;
        root = null;
        while (sc.hasNext()) {
            n = sc.nextInt();
            if (queue.isEmpty()) {
                root = createNode(n);
                queue.add(root);
                continue;
            }
            m = sc.nextInt();
            t = queue.peekFirst();
            queue.pop();
            t.left = createNode(n);
            t.right = createNode(m);
            if (t.left.value != -1)
                queue.add(t.left);
            if (t.right.value != -1)
                queue.add(t.right);
            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.

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post