Fill This Form To Receive Instant Help

Help in Homework
trustpilot ratings
google ratings


Homework answers / question archive /  A complete binary tree is a binary tree in which all the levels are completely filled except possibly the last level, which is filled from left to right

 A complete binary tree is a binary tree in which all the levels are completely filled except possibly the last level, which is filled from left to right

Computer Science

 A complete binary tree is a binary tree in which all the levels are completely filled except possibly the last level, which is filled from left to right.

You are expected to perform different types of commands on a complete binary tree as shown below:-

  •  - Insert nodes in the tree(each node should be inserted in O(1) time). Insertion needs to be level wise and from left to right.
  • To insert each node in O(1) you need to have an array which stores the address of the nodes in level order.(Address of root node should be stored at index 0 , address of left child of root node should be stored at index 1, address of right child of root node should be stored at index 2 and so on.)
  • 'a' - Find the sum of nodes with prime valued grandparent (i.e. sum of nodes whose grandparent stores a prime value).
  • 'b' - Given a level of the tree , you have to check if that level represents a palindrome of nodes. If it represents a palindrome of nodes then print the sum of nodes in that level otherwise print the sum of two extremes(sum of the left most node and the right most nodes in that level).
  • Example : let say the given level contains nodes with following values 11, 12, 12, 11(ordered from left to right) then it represents a palindrome and the output should be 11+12+12+11 = 46.
  • 'c' - Given an index of a node in the level order(index starts from 0),you have to find the zig-zag path from that node to a leaf node with maximum sum and print the maximum sum.
  • zig-zig path : zig-zag path is a path from a given node to a leaf node alternating between left and right node(explained in the sample input). From any node there are atmost two zig-zig paths possible.

Note:You have to use a class to make node. Provided class in just a basic one , you can define some member functions inside the class(Variables declared inside the class should be private).

 

 

class Node 
{
    private:
    int val;
    Node *left, *right;
    public: 
    Node(int x)
    {
        val = x;
        left = right = NULL;
    }

};

Input Format

  • The first line of input contains an integer N representing the number of commands to perform. Next subsequent N lines represent N commands. Commands can take values 'i' , 'a', 'b', 'c'.
  • If the command is 'i', it is followed by an integer m denoting the number of nodes to be added and m integers representing the data for each node respectively.
  • If the command is 'a', then no additional data follows.
  • If the command is 'b', then it is followed by an integer value representing level in the tree(root is at level 0).
  • If the command is 'c', then it is followed by an integer value representing the index of the node in the level order(indexing starts from 0).

Constraints

  • 1 <= N <= 104
  • 1<= Total nodes in the tree <=105
  • 1<= value stored in a node <=104

Output Format

  • If command is of type 'i', then no need to print anything.
  • If command is of type 'a', then print the sum obtained. If there are no such nodes with prime valued grandparent then print 0.
  • If command is of type 'b', then print the sum obtained.
  • If command is of type 'c', then print max value of zig-zag path from given node to the leaf.

Sample Input 0

8
i 11 1 2 2 3 4 3 4 5 6 5 6
a
b 0
c 0
b 1
b 2
c 6
c 4

Sample Output 0

22
1
12
4
7
4
10

Explanation 0

After the 1st command i (i.e. inserting nodes in the tree ) tree looks like:

 

  • Next query consists of command 'a', so the output will be 5+6+5+6=22.
  • Next query consists of command 'b' followed by the level in the tree, so the output will be 1. There is only 1 node at level 0 which represents a palindrome(a single node is palindrome always), therefore sum of nodes is 1.
  • Next query consists of command 'c' followed by the index of the node, so the output will be 12. There are 2 zig-zag paths possible X0->X1->X4->X9 and X0->X2->X5 you need to print max of path sum i.e. max(1+2+4+5,1+2+3) i.e. 12.
  • Next query consists of command 'b' followed by level of the tree. There are two nodes at level 1 with values 2, 2 respectively which represents a palindrome, therefore the ouput is 4(2+2).
  • Next query consists of command 'b' followed by level of the tree. There are four nodes at level 2 with values 3, 4, 3, 4 respectively which does not represent a palindrome, therefore the ouput is 7(3+4 i.e. sum of two extremes).
  • Next query consists of command 'c' followed by the index of the node and the given node itself is a leaf node so output is 4.
  • Next query consists of command 'c' followed by the index of the node and there are two paths possible, X4->X9 and X4->X10 so output is 10.

 

 

 

Contest ends in 3 days

Submissions: 4

Max Score: 70

Difficulty: Medium

Rate This Challenge:

    

More

 

Current Buffer (saved locally, editable)     

 

C++


 

 

 

1

 

#include <cmath>

2

#include <cstdio>

3

#include <vector>

4

#include <iostream>

5

#include <algorithm>

6

using namespace std;

7

?

8

?

9

 

int main() {

10

 

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   

11

    return 0;

12

}

13

?

Purchase A New Answer

Custom new solution created by our subject matter experts

GET A QUOTE