Count Complete Tree Nodes

Count the number of nodes in a complete binary tree in better than O(n) time. Compare the heights of the leftmost and rightmost paths: if equal, the subtree is perfect and contains 2^h - 1 nodes; otherwise recurse.

Examples
Input: [1,2,3,4,5,6]
Output: 6
Hints

Count Complete Tree Nodes

Count the number of nodes in a complete binary tree in better than O(n) time. Compare the heights of the leftmost and rightmost paths: if equal, the subtree is perfect and contains 2^h - 1 nodes; otherwise recurse.