Trees Interview Questions | Plagiarism Test

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 :

Create an empty queue q and a counter to store the size.

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).

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);
    }
}

[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.

Plagiarism Test

Concepts Used

Difficulty Level

Problem Statement :

Solution Approach :

Introduction :

Method 1 (using Queue):

Method 2 (Recursion) :

SOLUTIONS:

Leave a Reply Cancel reply

Memory Interleaving

Benefits of Multithreading

Lock Variable Synchronization Mechanism

Sleeping Barber problem in Operating System

Dekker’s Algorithm in Operating System

Bakery Algorithm in Operating System

Sign in to your account

Login via OTP

Login via OTP

Register with PrepBytes

Concepts Used

Difficulty Level

Problem Statement :

Solution Approach :

Introduction :

Method 1 (using Queue):

Method 2 (Recursion) :

SOLUTIONS:

Leave a Reply Cancel reply