Question:
Given a binary tree root node, get the average of all nodes in Binary Tree
Solution:
The sum of all the nodes is 121
Total number of nodes are :7
So the average is 121/7 = 17.2
Solution in C++
#include <iostream> #include <queue> #include <stack> using namespace std; // structure to hold binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; int total_sum = 0; int no_of_nodes = 0; void get_average(Node *node) { if (node == NULL) { return; } total_sum = total_sum + node->data; no_of_nodes = no_of_nodes + 1; get_average(node->left); get_average(node->right); } int main() { Node* root = nullptr; /* Binary tree: 16 / \ / \ 10 25 / \ / \ / \ / \ 7 15 18 30 */ root = new Node(16); root->left = new Node(10); root->right = new Node(25); root->left->left = new Node(7); root->left->right = new Node(15); root->right->left = new Node(18); root->right->right = new Node(30); get_average(root); cout<<"The average is "<<(total_sum/no_of_nodes)<<endl; return 0; }
Output:
The average is 17