Подсчитать среднее арифметическое значений узлов в идеально сбалансированном дереве. - С++

[vladrrom]

В файле input.txt хранится последовательность целых чисел.
По входной последовательности построить идеально сбалансированное дерево и подсчитать среднее арифметическое значений узлов.
Подскажите, пожалуйста, как записать нахождение среднего арифметического всех узлов дерева.
p.s. я понимаю, что при ф-ции обхода (по вашему мнению, какой лучше использовать обход в Идеал. Сбланс. дереве?) надо складывать информационные поля.
Код есть, но не доделанный:

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
 
ifstream in("input.txt");
ofstream out("output.txt");
 
struct tree {
    int inf;
    tree *right;
    tree * left;
};
tree *root;
 
void create(int number, tree *&root)
{
    int a;
    if (number > 0)
    {
        root = new tree;
        in >> a;  //считываем из файла in очередное число
        root->inf = a;
        root->left = root->right = NULL;
        int numberLeft = number / 2, numberRight = number - numberLeft - 1;
        create(numberLeft, root->left);
        create(numberRight, root->right);
    }
}
 
void search(int x, tree *root)
{
    if (root) // если дерево не пустое
        if (x == root->inf) /* и значение узла равно x,  то выводим сообщение об успешности поиска и выходим из подпрограммы */
        {
        cout << "search is successful";
        }
        else    {
            search(x, root->left); /* иначе  обходим левое и правое поддеревья */
            search(x, root->right);
        }
}
 
void preorder(tree *root)
{
    if (root)
    {
        cout << root->inf +  << "\t"; //складываем 
        preorder(root->left);
        preorder(root->right);
    }
}
 
int main(){
    int a;
    in >> a;
    create(a, root);
    in.close();
    out.close();
    return 0;
}