222k views
0 votes
Given the following definition of a node and binary search tree, write the member functions described below. You may declare and implement more functions if you need but you need to fully code any function you call however, you may not declare additonal data members. Any function you call will calculate towards runtime of your function.

Please ensure that the run time requirement is met to get full marks

class BST struct Node int data_; Node* left_; Node* right_; Node(int dat) data_=dat; left_=right_=nullptr; ; Node* root_; ... ;

rite the following member functions of BST: int BST::nodeDifference() const; This function returns the difference between the number of nodes in the right subtree and the left subtree. Use the formula: number of nodes in right subtree - number of nodes in the left subtre If the tree is empty, function returns 0. Runtime requirement O(n) For example given the tree below nodeDifference() would return -3 because there are 3 nodes on the right (40,45 and 50) and 6 nodes in the left (5,10,15,20,25,30). Thus, 3 - 6 = -3

User Dekike
by
8.6k points

1 Answer

1 vote

Here's the implementation of the `nodeDifference` member function in the `BST` class that calculates the difference between the number of nodes in the right subtree and the left subtree:

```cpp

class BST {

private:

struct Node {

int data_;

Node* left_;

Node* right_;

Node(int data) : data_(data), left_(nullptr), right_(nullptr) {}

};

Node* root_;

public:

// Other member functions...

int nodeDifference() const {

return nodeDifferenceHelper(root_);

}

private:

int nodeDifferenceHelper(Node* node) const {

if (node == nullptr) {

return 0;

}

int leftCount = countNodes(node->left_);

int rightCount = countNodes(node->right_);

return rightCount - leftCount;

}

int countNodes(Node* node) const {

if (node == nullptr) {

return 0;

}

return 1 + countNodes(node->left_) + countNodes(node->right_);

}

};

```

In this code, the `nodeDifference` member function calls the `nodeDifferenceHelper` function to calculate the difference between the number of nodes in the right subtree and the left subtree. If the tree is empty (root is `nullptr`), the function returns 0.

The `nodeDifferenceHelper` function recursively traverses the tree and counts the number of nodes in the left and right subtrees using the `countNodes` helper function. It then returns the difference between the counts.

The `countNodes` function is a recursive function that counts the number of nodes in a subtree. It starts by checking if the current node is `nullptr`. If so, it returns 0. Otherwise, it counts the current node and recursively calls `countNodes` on the left and right subtrees, adding their counts.

The runtime requirement of this implementation is O(n) since it needs to traverse all the nodes in the tree once to count them.

User VeenarM
by
8.0k points

No related questions found