---
description: '# Medium'
---

# 222. Count Complete Tree Nodes

{% hint style="info" %}
Three approaches:

1. DFS traversal all nodes, and count at the same time
2. BFS traversal all nodes, and count at the same time
3. Strategy:&#x20;
   1. If `height(root.left) = height(root.right)`, then $$n = 2^{height+1}$$&#x20;
   2. If `height(root.left) > height(root.right)`, then  `n = 1+nums(root.left)+nums(root.left)`
{% endhint %}

{% tabs %}
{% tab title="Python(I)" %}
```python
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        # DFS
        # edge case
        if root == None:
            return 0
        
        stack = [root]
        n = 0
        while len(stack) != 0:
            root = stack.pop()
            n = n + 1
            if root.left != None:
                stack.append(root.left)
            if root.right != None:
                stack.append(root.right)
                
        return n
```

Because traversal all nodes, time complexity = $$O(n)$$ , space complexity = $$O(n)$$&#x20;
{% endtab %}

{% tab title="Python(II)" %}
```python
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        # BFS
        # edge case
        if root == None:
            return 0
        
        queue = [root]
        n = 0
        while len(queue) != 0:
            l = len(queue)
            for i in range(l):
                root = queue.pop(0)
                n = n + 1
                if root.left != None:
                    queue.append(root.left)
                if root.right != None:
                    queue.append(root.right)
        return n
```

Because traversal all nodes, time complexity = $$O(n)$$ , space complexity = $$O(n)$$&#x20;
{% endtab %}

{% tab title="Python(III)" %}
Time complexity = $$O(n)$$ , space complexity = $$O(1)$$ . This is the worst case, generally it's not necessary to traversal all nodes.&#x20;

Be careful with two points:

1. $$1+2^1+2^2+...+2^n = 2^{n+1}-1$$&#x20;
2. Height of left subtree is always to traversal left child, Height of right subtree is always to traversal right child. Because we want to find `max` height of left subtree and `min` height of right subtree.

```python
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        # edge case
        if root == None:
            return 0
        
        # regular case
        left = self.leftHeight(root.left)
        right = self.rightHeight(root.right)
        if left == right:
            n = pow(2, left+1) - 1
        else:
            n = 1 + self.countNodes(root.left) + self.countNodes(root.right)
            
        return n
    
    def leftHeight(self, root):
        # stop condition
        if root == None:
            return 0
        
        return 1 + self.leftHeight(root.left)
        
    def rightHeight(self, root):
        # stop condition
        if root == None:
            return 0
        
        return 1 + self.rightHeight(root.right)
```
{% endtab %}

{% tab title="" %}

{% endtab %}
{% endtabs %}
