Count Complete Tree Nodes

07/16/2016 Tree Binary Search


Given a complete binary 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 and nodes inclusive at the last level h.


Result: Accepted Time: 176 ms

Here should be some explanations.

class Solution {
    int helper(TreeNode * root)
            return 0;
        int leftside=0, rightside=0;
        TreeNode *l=root, *r=root;
        while(l) leftside++,l=l->left;
        while(r) rightside++, r=r->right;
            return (1 << rightside)-1;
        return helper(root->left)+helper(root->right)+1;
    int countNodes(TreeNode* root) {
        return helper(root);

Complexity Analytics

  • Time Complexity:
  • Space Complexity: