Optimal Approach

Algorithm

Given that the binary is a complete binary tree, we can exploit its properties to optimise the algorithm and achieve a better time complexity.

In a complete binary tree, the last level may not be completely filled, but the nodes are positioned from left to right. This property allows us to determine the number of nodes using just the height.

The relationship between the height of the binary tree (h) and the maximum number of nodes it can have, denoted by the formula:

Maximum Number of Nodes: 2^h-1

If the last level of a binary tree is perfectly filled, known as a perfect binary tree, the count of nodes can be determined by the formula: 2h-1, where h is the height. To check if the last level of the Binary Tree is filled or not we can compare the left and right heights of the tree.

If the left height equals right height, it indicates that the last level is completely filled.If the left height does not equal right height, the last level is not completely filled.

In the case where left height and right height differ, we can employ a recursive approach. We recursively calculate the number of nodes in the left subtree and in the right subtree , and then return the total count as 1 + leftNodes + rightNodes.

If the height of the left subtree is equal to the height of the right subtree, we can directly calculate using the 2h-1 formula.

Base Case: If the given node is null, we return 0 as there are no nodes to count.
Recursive Calls: Recursively find the left height and right height of the Binary Tree.
Comparison: If the left height is equal to the right height, it implies that the tree’s last level is completely filled. Return the count of nodes using the formula: return (1 << lh) - 1, where << represents the left shift operator and represents the power of 2.

If the left height is