• Time:O(n)
• Space:O(h)

## C++

``````class Solution {
public:
int countNodes(TreeNode* root) {
if (!root)
return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
``````

## JAVA

``````class Solution {
public int countNodes(TreeNode root) {
if (root == null)
return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
}
``````

## Python

``````class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return 1 + self.countNodes(root.left) + self.countNodes(root.right)
``````

## Approach 2: Heuristic

• Time:O(\log^2n)
• Space:O(h)

## C++

``````class Solution {
public:
int countNodes(TreeNode* root) {
if (!root)
return 0;

TreeNode* l = root;
TreeNode* r = root;
int heightL = 0;
int heightR = 0;

while (l) {
++heightL;
l = l->left;
}

while (r) {
++heightR;
r = r->right;
}

if (heightL == heightR)  // root is a complete tree
return pow(2, heightL) - 1;
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
``````

## JAVA

``````class Solution {
public int countNodes(TreeNode root) {
if (root == null)
return 0;

TreeNode l = root;
TreeNode r = root;
int heightL = 0;
int heightR = 0;

while (l != null) {
++heightL;
l = l.left;
}

while (r != null) {
++heightR;
r = r.right;
}

if (heightL == heightR) // root is a complete tree
return (int) Math.pow(2, heightL) - 1;
return 1 + countNodes(root.left) + countNodes(root.right);
}
}
``````

## Python

``````class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0

l = root
r = root
heightL = 0
heightR = 0

while l:
heightL += 1
l = l.left

while r:
heightR += 1
r = r.right

if heightL == heightR:  # root is a complete tree
return pow(2, heightL) - 1
return 1 + self.countNodes(root.left) + self.countNodes(root.right)
``````