Count Complete Tree Nodes

Given a

completebinary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:

In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2^{h}nodes inclusive at the last level h.

if countLeft == countRight, return count(countLeft)

else return countNodes(root->left) + countNodes(root->right) + 1;

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int countNodes(TreeNode* root) { if(root == nullptr) return 0; int left = countLeftLevel(root); int right = countRightLevel(root); if(left == right){ return count(left); } else{ return countNodes(root->left) + countNodes(root->right) + 1; } } int countLeftLevel(TreeNode* root){ int count = -1; while(root){ count++; root = root->left; } return count; } int countRightLevel(TreeNode* root){ int count = -1; while(root){ count++; root = root->right; } return count; } int count(int n){ int sum = 1; int factor = 2; while(n--){ sum += factor; factor *= 2; } return sum; } };