Plagiarism Test

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 go through best online learning sites for programming to use 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:

#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;
        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);
    }
}
Previous post Sum Query
Next post Copying Hero

Leave a Reply

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