Please need help with this; In call of duty, the only goal to accomplish is to maximize your enemies taken out and thus have the highest K/D in the lobby. So now you are playing Call of Duty: World at War (The best call of duty game ever) and you have reached a place with a large staircase in front of you. And there is an enemy at each landing of the staircase (on the left side and the right side of each step of the staircase). The staircase is analogous to a binary tree with each of its nodes as a landing of the staircase and each of its edges as stairs from one landing to another. Given the following binary search tree

You start with person 8 and you take that person out, and then you move left or right. You want to take out the maximum possible number of enemies. You can take out every person you can see from your position with your suppressed sniper gun. But you can see only the persons at the leftmost standing at each level and cannot see the rest.

Before starting shooting them, you want to know how many persons you can take out. You are busy keeping an eye on the enemies. So you want this program to find out the maximum number of people you can take out from that location by providing with the analogous a binary search tree.

[ Note: Players do not change their position after one player has been taken out, i.e. the leftmost node remains the same even after player on that node has been taken out. Or we can say that the nodes are not removed after the player on that node has been taken out. ]

In other words, you need to find the maximum number of left children on a path of the binary search tree. The input for your program will be an integer (> 0) that denotes the amount of test cases then the numbers to be inserted into a binary search three. The output will be a number that denotes the maximum number of enemies that can be taken out. You will also need to implement a binary search tree type.

template

class bst

{

struct binTreeNode

{

binTreeNode * left ;

binTreeNode * right ;

Type item ;

};

public :

class binTreeIterator

{

public : friend class bst;

binTreeIterator ();

binTreeIterator ( binTreeNode *);

bool operator ==( binTreeNode *);

bool operator ==( binTreeIterator );

binTreeIterator rightSide ();

binTreeIterator leftSide ();

private :

binTreeNode * current ;

};

bst ();

bst ( const bst < Type >&);

const bst& operator =( const bst < Type >&);

~bst ();

void insert ( const Type &);

binTreeIterator begin ();

binTreeIterator end ();

private :

binTreeNode * insert ( binTreeNode * , const Type &);

void destroyTree ( binTreeNode *);

void cloneTree ( binTreeNode * , binTreeNode *);

binTreeNode * root ;

};

Each member contains and performs the following

struct binTreeNode - is the binary tree node, each node contains some item and a pointer to the left and right child

class binTreeIterator - is basically going to be a pointer to traverse the binary search tree, but we will use this iterator to hide pointer info in main and still allow us to navigate the binary search tree, each member of binTreeIterator will be as follows

binTreeNode * current - stores the pointer of a node that the iterator points to

binTreeIterator() - is the default constructor that sets current to NULL

binTreeIterator(binTreeNode*) - is a constructor that sets current with the pointer passed into the constructor

bool operator==(binTreeNode*) - returns true if current equals the pointer on the right hand side of the operator and false otherwise

bool operator==(binTreeIterator) - returns true if current equals the right hand side iterator objects current and false otherwise

binTreeIterator rightSide() - returns an iterator object that is on the right side of the iterator that calls the function

binTreeIterator leftSide() - returns an iterator object that is on the left side of the iterator that calls the function

binTreeNode * root - is a pointer that points to the root of the binary search tree

bst() - is the default constructor that sets root to NULL

bst(const bst&) - is the copy constructor, it will call cloneTree by passing in root and copy.root (copy is the object passed into the constructor)

const bst& operator=(const bst&) - is the default assignment operator, it will check for self assignment and call destroyTree and cloneTree if the objects arent the same and then returns *this

~bst() - is the destructor that deallocates the binary search tree, it will just call destroyTree

void insert(const Type&) insert an item into the binary search tree, this function will call the private insert function if we do not have an empty binary search tree (and that function will recursively insert the element), the public insert is simply a wrapper

binTreeIterator begin() - returns an iterator that contains the root pointer, return binTreeIterator(root)

binTreeIterator end() - returns an iterator that contains a NULL pointer, return binTreeIterator(NULL)

binTreeNode* insert(binTreeNode*, const Type&) - this private function will insert an element into the binary search tree, this function is recursive

void destroyTree(binTreeNode*) - deallocates the binary search tree, this will be a postorder method of deallocating the tree

void cloneTree(binTreeNode*, binTreeNode*) - this creates a deep copy of the tree, this will copy the children of the second parameter into the the children of the first parameter and recursively continue this step for the left and right have of the binary search tree (this is more complicated version of preorder)

Contents of main

In main, you will

1. Read the number of test cases

2. Read nodes and insert each into the binary search tree one by one until you read -1

3. Output the max number of enemies that can be taken out

4. Repeat step 2 if more test cases exist

In order to output the max enemies, you will need a recursive function in main that will traverse the bst object using binTreeIterator, the function prototype is

int findMaxEnemyTakeOuts (bst binTreeIterator )

The way this function is written is that it returns all the max number of enemies not including the root, so in main, we have cout << findMaxEnemyTakeOuts(binSearchTree->begin()) + 1 << endl; and binSearchTree is a pointer that points to a bst object.

This function sort of follows postorder traversal of a binary tree. Thus you compute the max enemies on the left side, the compute the max enemies on the right side, and the max number of the two gets returned up the binary tree. Remember an enemy on the left side counts as 1 enemy take out and an enemy on the right does not count as an enemy take out (all though there could be a sub tree for the right side, but the immediate right node is not a take out).

Sample Input:

you can use those tree input to test the program.

3

1st input

8

10

3

14

13

6

4

7

1

-1

2nd input

1 0

-1

3rd input

3

4

-1

Sample Output

Case 1 : 3

Case 2 : 1

Case 3 : 1

Case 4 : 2

Case 5 : 6