Instructions

The class BST creates binary search trees by using dynamic nodes that have two pointers, one for the right child and one for the left child.

The member variables of the class are:

A pointer named root that points to the root of the tree$$the root is a dynamic object of type Node.

A variable of type int named count that keeps track of the number of nodes in the tree.

The class BST uses the class Node, which includes the class BST as a friend class. This will allow you to access the private member variables of the class Node directly, simplifying the implementation when using pointers.

class Node

$\{$

friend class BST;

public:

Node$()$ : data$(0),$ rlink$($nullptr$),$ llink$($nullptr$)\{\}$

~Node$()\{\}$

private:

int data;

Node $*$rlink$,*$llink;

$\}$;

class BST

$\{$

public:

$//$ member functions

private:

Node $*$root; $//$pointer to the root

int count; $//$number of nodes

$\}$;

Your job is to write the definition of three member functions of the class BST as indicated below.

Function search$()$

Parameters: An int storing the element to search.

The return value is a Boolean type.

The function searches the tree for the element passed by the parameter and it returns true if the element is found, or false otherwise.

Do not use $0/1$ as a return type. This is C$++,$ not C$.$ Even though $0/1$ works, using $$true$$ and $$false$$ is preferred in C$++$ because it improves code readability and enhances code semantics.

This is not a recursive function.

Function totalLeaves$()$

This function traverses the whole tree and returns the number of leaves in the tree.

The return value is an int type.

This is not a recursive function.

You will need to use an STL stack of pointers to objects of type Node, which will store pointers to the nodes visited in the tree. This is how to do it:

Start by pointing to the root.

$($Outer loop$)$ Loop until the pointer is a nullptr or there are no more pointers stored in the stack.

$($Inner loop$)$ Loop to go down to the leftmost node and, for each node, store the address $($pointer$)$ into the stack.

At the end of the inner loop, the leftmost node's address $($pointer$)$ should be at the top of the stack.

Remove the pointer from the stack and go to the right link of the node to which the pointer is pointing, and start the outer loop again.

The pseudocode above does not include all the details, of course, and it does not tell when and how you need to count the number of leaves, but it gives you a start to figure this out.

The implementation should consist of approximately $15-18$ statements $($excluding the header, curly brackets, comments, or blank lines$).$ If your code exceeds this length, you are overcomplicating the implementation. If that is the case, consider tracing a small tree with only four nodes to determine how to make the implementation more concise.

Function totalParentsOneChild$()$

This function traverses the whole tree and returns the number of nodes that have only one child.

The return value is an int type.

This is not a recursive function.

The implementation is similar to the previous function, but slightly longer.

There are $8$ trees tested for each function. The preorder and inorder traversals will be printed so that you can figure out how the trees are structured $($from one of the exercises, recall that any binary tree has a unique combination of preorder and inorder traversals$).$

Assumption: The tree has at least one node.

Help me in C$++$ PLEASE