CareerCup

int findDiff(root)
{
	if(!root)
		return 0;
	l=0;r=0;
	l=findDiff(root->left);
	r=findDiff(root->right);

	root->val=l-r;
	return l+r+1;
}

Please let me know if anything is missing.

Sorry it should be total number of nodes in the left sub-tree..

Sorry it should be total number of nodes in the left sub-tree..

fun(Node n) {
      int lval = fun(n.left), rval = fun(n.right);
      n.value = lval - rval;
      return lval + rval;
}

// Node definition can be derived from above code.

// Looks like I was logged in. So posting again.

fun(Node n) {
      if (n == null) return 0;
      int lval = fun(n.left), rval = fun(n.right);
      n.value = lval - rval;
      return lval + rval;
}

Assume Node has (int) data as member:

public int LeftMinusRight(Node root)
{
return Sum(root.Left) - Sum(root.Right);
}

private int Sum(Node node)
{
return Sum(node.Left) + Sum(node.Right);
}