Count Nodes in Complete Binary Tree

Given a complete binary tree root, return the number of nodes in the tree.

This should be done in \(\mathcal{O}((\log n)^2)\).

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Count-Nodes-in-Complete-Binary-Tree

Examples

Example 1

Input

• root =

Output

• answer = 5

Example 2

Input

• root =

Output

• answer = 7

Solution