CareerCup

void avg(node *root,int *sum,int *count)
{
     if(root)
     {
             *sum  = *sum + root->data;
             *count = *count + 1;
             cout<<root->data<<" "<<*sum<<" "<<*count<<endl;
             avg(root->left,sum,count);
             avg(root->right,sum,count);
     }
     else return;
}

Implement the two function , one call the another with the sum and counter pointers. In the second function iterate the tree in inorder and calculate sum and no of element.
Return to the main function now sum and counter pointer has their values so calculate the avg and return.

employ typical dfs/bfs, with little modification to count number of nodes encountered and sum of the values of node.
When traversal ends, get the average

O(log n). Same as counting number of nodes and additional step is to copy the value. After the function returns take the avg
print avg (node* root)
{
int value = 0;
int data = 0;
if(node==null)
{
printf("%d",data/value);
return;

}
else
{

data+=node->left+data;
value++;
data+=node->data;
value++;
data+=node->right+data;
value++

avg(node->left);
avg(node->right);
}

print avg (node* root)
{
int value = 0;
int data = 0;
if(node==null)
{
printf("%d",data/value);
return;

}
else
{

data+=node->data;
value++;
avg(node->left);
avg(node->right);
}

Easiest way is to write 2 function. 1 to calculate sum and another to calculate num of element and then divide.

If want to do in a single method then.
1- do post order traversal.
2- pass num of element, num, avg to the calling function.

int avg (Node root,int arr[])
{
if (root.left != null){
avg(root.left,arr);

if (root.right!= null){
avg(root.right,arr);

arr[0] += root.data;
arr[1]+=1;
arr[2] = arr[0]/arr[1];
return arr[2];
}

avg(

Use 2 variables to keep track of sum and count of nodes respectively.
Do a traversal of entire tree and return sum/count at end.

int getAverage(Node *root) {
    int sum = 0;
    int count = 0;
    
    traverseTreeForAverage(root, &sum, &count);
    
    if (count == 0) {
       return 0;
    } else {
       return sum/count;
    }
}

void traverseTreeForAverage(Node* node, int *sum, int *count) {
    if (node != null) {
       *sum += node->value;
       *count += 1;

       traverseTreeForAverage(node>left);
       traverseTreeForAverage(node>right);                           
    }
}

int avg(NODE *head) // helper function that recursively calls the sume function
{
int count=0;
int sum=sume(head,&count);
return sum/count;
}

int sume(NODE *head,int *p)
{

if(head==NULL)
{
return 0;
}
else
{
*p=*p+1;
}
return(sume(head->right,p)+sume(head->left,p)+head->value);
}

I have made the sum return from the sume function as a return value, wheras the count is intialized as 0 and passed in recursive function by reference.

You divide the sum with count and return the avg from the helper function

int avg(NODE *head)             // helper function that recursively calls the sume function
{
	int count=0;
	int sum=sume(head,&count);
	return sum/count;
}

int sume(NODE *head,int *p)
{
	
	if(head==NULL)
	{
		return 0;	
	}
	else
	{
		*p=*p+1;
	}
	return(sume(head->right,p)+sume(head->left,p)+head->value);
}

I have made the sum return from the sume function as a return value, wheras the count is intialized as 0 and passed in recursive function by reference.

You divide the sum with count and return the avg from the helper function

u can implement thsi in only one function :)
just use one extra vraible as a para,mter

intialy pass c as a value zero:
int sumavg(struct node *t,int c)
{
static int n;
int sum;
if(!t)
return 0;

sum=t->info+sumavg(t->left,1)+sumavg(t->right,1);
if(c==1)
return sum;

return (sum/n);
}

Passing the sum and count variables as parameters seem to be wrong since we don't have a track when the recursion has traversed all the nodes.
Keep sum and count as global variables or class variables in java.
No need to pass any parameters.

Time : O(n)

// sum and count are class variables.
// sum = 0; count = 0; before calling avg.
// call this function as avg(rootNode).
// after the function call, avg = sum / count;

public static void avg(Node node)
    {
      if(node == null)
      {
        // System.out.println(sum + " " + count);
        return;
      }
      else
      {
        sum += node.value;
        count++;
        avg(node.left);
        avg(node.right);
      }
    }

Traversing Nodes in the tree level order and summing up value as you visit. Additional Q required to store each level.

Queue<Node> queue = new LinkedList();
Node flagNode = new Node(00);
int avg = 0;
int sum =0;
int count = 0;
queue.add(rootNode);
queue.add(flagNode);
while (!queue.isEmpty()) {
Node node = queue.poll();
// System.out.print("While Condition Values "+node.value);
if (node != flagNode) {
sum = sum + node.value;
System.out.print(node.value+ " ");
//System.out.println("Sum"+sum);
count++;
if (node.leftChild != null) {
queue.add(node.leftChild);
//sum = sum + node.leftChild.value;
}
if (node.rightChild != null) {
queue.add(node.rightChild);
// sum = sum + node.rightChild.value;
}
} else if (!queue.isEmpty()) {
// System.out.println("Adding Flag");
queue.add(flagNode);
}
}
System.out.print("Sum"+sum);
avg = sum / count;
System.out.print("Avg"+avg);
}

guys , all your algorithms are correct, and they are all same , traverse the tree and sum the values and keep a variable for count,

thats simple logic of all the replies above,

Amazon needs something more better than that,
I also said the same algorithm in the interview , thay are expecting something else as a response and not as simple as that.

float avg(NODE *node){
	static int sum = 0;
	static int count = 0;
	
	if(node){
	sum += node->data;
	count++;
	avg(node->left);
	avg(node->right);
	}

	if (count)
		return sum / count;
}

int avg(Node n)
{
if(!n) return 0;

if(isLeaf(n)) return (n->data);
else
return ( avg(n->left) / 2 + avg(n->right)/2 )
}