{"id":2370,"date":"2020-06-22T18:00:23","date_gmt":"2020-06-22T18:00:23","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2370"},"modified":"2022-03-30T23:07:48","modified_gmt":"2022-03-30T23:07:48","slug":"plagiarism-test","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/plagiarism-test\/","title":{"rendered":"Plagiarism Test"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

BFS , Recursion<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given a binary tree, and a node X<\/code>, we have to sum all the nodes except the node X<\/code>.
\nSee example in the link given below.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h4>\n

Introduction :<\/h4>\n
\n

Idea is to traverse all the nodes except X<\/code> and add the values of the nodes to the answer.
\nWe can any traversal method to perform this operations.<\/p>\n<\/blockquote>\n

Method 1 (using Queue):<\/h4>\n
\n

We can use a queue to perform level order traversal<\/strong>. We will perform following operations :<\/p>\n

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

      Method 2 (Recursion) :<\/h4>\n
      \n

      Introduction says it all, all we need is to sum up the values left<\/strong> node & right<\/strong> node recursively and discard the node when it is X<\/code>.
      \nWe will do the same for left<\/strong> & right<\/strong> subtrees by recursively calling , root->left<\/code> & root->right<\/code>.<\/p>\n<\/blockquote>\n

      SOLUTIONS:<\/h3>\n\t\t\t\t\t\t