Problem description:

Given a complete binary tree, count the number of nodes.

Note:

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 2h nodes inclusive at the last level h.

Example:

Input:
1
/ \
2 3
/ \ /
4 5 6

Output: 6

Solution:

A complete binary tree means every level is filled except for perhaps last level. To the extent that the last level is filled, it is filled left to right.
Therefore, we can know the following things.

  1. from traverse left subtree, we can obtain the maximum height of the tree.
  2. if the tree is perfect binary tree(complete and full), it will have 2^h -1 nodes

We use two pointer to count the height of left and right. If they’re equal, then the subtree of this root have totally 2^h -1 nodes. If not equal, then we recursively search root->left and root->right.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* 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) return 0;
        
        int hl= 0, hr= 0;
        TreeNode* l= root, *r= root;
        while(l){ hl++; l= l->left;}
        while(r){ hr++; r= r->right;}
        
        if(hl== hr) return pow(2, hl)-1;
        else return 1+countNodes(root->left)+ countNodes(root->right);
    }
};

time complexity:

reference:
https://goo.gl/SAq511
https://goo.gl/o9PEje