Տրված է երկուական փնտրման ծառ, որի յուրաքանչյուր հանգույց (node) պարունակում է ինչ-որ ամբողջ թիվ։ Գտնել այդ թվերի միջին թվաբանականը։ Ալգորիթմի պահանջվող բարդությունն է O(n):

bst average

#include <iostream>
#include <stdlib.h>

struct node
{
	struct node* left;
	struct node* right;
	int data;
};

struct node* new_node(int d)
{
	struct node* n = (struct node*)malloc(sizeof(struct node));
	n->left = 0;
	n->right = 0;
	n->data = d;
	return n;
}

void sum(struct node* n, int& s, int& c)
{
	if(n == 0)
	{
		return;
	}
	sum(n->left, s, c);
	++c;
	s += n->data;
	sum(n->right, s, c);
}

int average(struct node* n)
{
	int s = 0;
	int c = 0;
	sum(n, s, c);
	return s/c;
}

int main()
{
	struct node* r = new_node(1);
	r->left = new_node(2);
	r->left->left = new_node(4);
	r->left->right = new_node(3);
	r->right = new_node(5);
	int a = average(r);
	std::cout << " Average = " << a << std::endl;
	return 0;
}