# 222. Count Complete Tree Nodes

### Description

Given a **complete** binary tree, count the number of nodes.

**Note:**

**Definition of a complete binary tree from** [**Wikipedia**](http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees)**:**\
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

### Constraints

### Approach

### Links

* GeeksforGeeks
* Leetcode
* ProgramCreek
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:**

\[1, 2, 3, 4, 5, 6]

<div align="left"><img src="https://1091135627-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEmU-aGQcUvtjjAH8_3%2F-MK-iyaVTmcVdM_f331r%2F-MK-jcFQ7aw-WoNwklpQ%2Fimage.png?alt=media&#x26;token=f961ec26-d7ac-4b53-b231-28e37cbd846e" alt=""></div>

**Output:**

6
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="TreeNode" %}

```java
// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
```

{% endtab %}

{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(N)
 * Space complexity : O(d)=O(logN) to keep the recursion stack, 
 *    where d is a tree depth.
 */

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

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */
 
 class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
        
        int left = getLeftHeight(root) + 1;
        int right = getRightHeight(root) + 1;
        
        if(left == right) {
            return (2 << (left-1))-1;
        }
        
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
    
    private int getLeftHeight(TreeNode node) {
        if(node == null) return 0;
        
        int height = 0;
        while(node.left != null) {
            height++;
            node = node.left;
        }
        return height;
    }
    
    private int getRightHeight(TreeNode node) {
        if(node == null) return 0;
        
        int height = 0;
        while(node.right != null) {
            height++;
            node = node.right;
        }
        return height;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*