All Kinds Of Node Depths

• Time : O(n)
• Space : O(1)

using namespace std;

class BinaryTree {
public:
  int value;
  BinaryTree *left;
  BinaryTree *right;

  BinaryTree(int value) {
    this->value = value;
    left = nullptr;
    right = nullptr;
  }
};

void helper(BinaryTree* node, int& res, int depth = 0) {
	if(!node) return;
	res += depth * (depth + 1) / 2;
	helper(node->left, res, depth + 1);
	helper(node->right, res, depth + 1);
	return;
}

int allKindsOfNodeDepths(BinaryTree *root) {
  int res = 0;
	helper(root, res);
  return res;
}