Height Balanced Binary Tree

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

using namespace std;

// This is an input class. Do not edit.
class BinaryTree {
public:
  int value;
  BinaryTree *left = nullptr;
  BinaryTree *right = nullptr;

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

pair<bool, int> helper(BinaryTree* tree, int depth = 0) {
	if(!tree) return {true, depth};
	auto [lb, ld] = helper(tree->left, depth + 1);
	if(!lb) return {false, -1};
	
	auto [rb, rd] = helper(tree->right, depth + 1);
	if(!rb) return {false, -1};
	
	int mi = min(ld, rd);
	int ma = max(ld, rd);
	if(ma - mi > 1) return {false, -1};
	return {true, ma};
}

bool heightBalancedBinaryTree(BinaryTree *tree) {
  return helper(tree).first;
}