问题描述:

I am trying to find the sum and average of data of type `int`

from a longest path of a BST. I've made the following functions :

`int table::longest(){`

return longest(root);

}

int table::longest(node* curr){

int suml = 0;

int sumr = 0;

if(!curr)

return 0;

int hleft = height(curr->left);

int hright = height(curr->right);

if(hleft > hright){

suml = curr->data;

return suml += longest(curr->left);

}

sumr = curr->data;

return sumr += longest(curr->right);

}

int table::height(node* curr){

if(!curr)

return 0;

int hLeft = 1 + height(curr->left);

int hRight = 1 + height(curr->right);

if(hLeft > hRight)

return hLeft;

return hRight;

}

The function `longest`

returns me the sum of the data, but how to return its average without traversing the tree again in order to figure out how many nodes are in the longest path?

EDIT: The prototype of private function `longest`

has to be `int longest(node* root)`

and it has to return the average or at least the sum of the elements to the public function so it can return the average knowing the sum

Your code is not optimized. Unnecessary repeating the traversal is never recommended. You can use the given below function. It will do the task in O(n) time, where n is the number of nodes in binary tree.

```
int maxHeight = 0;
int longestPathSum = 0;
int table::longest(){
longest(root, 0, 0);
return longestPathSum;
}
void table::longest(node* curr, int sum, int height){
if(curr == NULL) return 0;
sum += curr->data;
if(++height > maxHeight) {
maxHeight = height;
longestPathSum = sum;
}
longest(curr->left, sum, height);
longest(curr->right, sum, height);
}
```

find the sum and average of data of type int from a longest path of a BST

sum = longestPathSum;

average = longestPathSum / maxHeight;

Instead of function 'longest' returning the sum of weights, you can pass the sum of weights and height as reference. This will allow not traversing the BST twice.

您可能感兴趣的文章：

- scala - The argument types of an anonymous function must be fully known. (SLS 8.5)
- c# - MySQL Parameters not adding values
- How to know the camera have captured the clear image in the iOS?
- jquery - After an ajax update to page, clicking a new link then back button shows outdated content in Chrome
- iphone - Converting UITextField ( field.text) NSString * to char *?
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**-
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?
- git svn - git svn fetch does not fetch a Subversion commit message modified after initial clone
- java me - Why I am getting the bad length exception when I am running this application?
- java - How to get string.format to complain at compile time
- ruby on rails - Trigger observer of parent class on change
- python - Issue with URL pattern in Django with webmonkey tutorial