Count Nodes in Complete Binary Tree

mediumSave

Binary SearchBinary TreeTree

Given a Complete Binary Tree, count the number of nodes in the tree. A Complete Binary Tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Example 1

Input

Output

Explanation. All nodes on every level are filled, thus there are 3 nodes.

Example 2

Input

Output

Explanation. The last level of the tree is not completely filled, but it's filled from left to right. There are 5 nodes in total.

Example 3

Input

Output

Explanation. The last level is partially filled, but all previous levels are fully filled. There are 6 nodes in total.

Example 4

Input

[
  [
    1
  ]
]

Output

Explanation. There is only one node in the tree.

Follow-up: Can you solve the problem using a method more efficient than calculating the height of the tree first and using it in a recursive function?

Constraints:

The tree will have the minimum of 1 node and maximum of 100000 nodes. Nodes of the tree are numbered from 1 to N.

Views: 2