# Count Complete Tree Nodes
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-complete-tree-nodes)
Canonical: https://scaleengineer.com/dsa/problems/count-complete-tree-nodes
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Dunzo](https://scaleengineer.com/companies/dunzo)
---
## Problem
Given the `root` of a **complete** binary tree, return the number of the nodes in the tree.

According to **[Wikipedia](http://en.wikipedia.org/wiki/Binary%5Ftree#Types%5Fof%5Fbinary%5Ftrees)**, every level, except possibly the last, is completely filled in a complete binary tree, 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`.

Design an algorithm that runs in less than `O(n)` time complexity.

**Example 1:**

![](https://assets.glich.co/dsa/count-complete-tree-nodes/image0.jpg) 

**Input:** root = [1,2,3,4,5,6]
**Output:** 6

**Example 2:**

**Input:** root = []
**Output:** 0

**Example 3:**

**Input:** root = [1]
**Output:** 1

**Constraints:**

* The number of nodes in the tree is in the range `[0, 5 * 104]`.
* `0 <= Node.val <= 5 * 104`
* The tree is guaranteed to be **complete**.

# Approaches
## Simple DFS Traversal
The most straightforward approach is to traverse the entire tree using DFS (Depth First Search) and count all nodes.
**Time:** O(n) where n is the number of nodes in the tree · **Space:** O(h) where h is the height of the tree, due to recursive call stack
**Pros:** Simple to implement; Works for any binary tree; Easy to understand
**Cons:** Doesn't utilize the complete binary tree property; Visits every node in the tree; Not optimal for complete binary trees
### Explanation
We can use a simple recursive DFS approach to traverse through all nodes of the tree. For each node, we add 1 to our count and recursively process the left and right children.

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

This solution will visit every node exactly once. While simple to implement, it doesn't take advantage of the complete binary tree property.
### Algorithm
1. If root is null, return 0
2. Recursively count nodes in left subtree
3. Recursively count nodes in right subtree
4. Return 1 (current node) + left count + right count

## Level Order Traversal
Using level order traversal (BFS) to count nodes level by level. This approach is still O(n) but provides a different way to count nodes.
**Time:** O(n) where n is the number of nodes in the tree · **Space:** O(w) where w is the maximum width of the tree
**Pros:** Visits nodes level by level; Iterative approach (no recursion); Good for visualizing tree structure
**Cons:** Still doesn't utilize complete binary tree property; Uses extra space for queue; Not optimal for complete binary trees
### Explanation
We use a queue to perform level order traversal. We process nodes level by level and increment our counter for each node we encounter.

```java
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int count = 0;
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            count++;
            
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        
        return count;
    }
}
```
### Algorithm
1. If root is null, return 0
2. Initialize a queue with root node
3. While queue is not empty:
   - Poll node from queue
   - Increment count
   - Add left and right children to queue if they exist
4. Return count

## Binary Search with Height Properties
This optimal approach utilizes the properties of a complete binary tree to perform a binary search on the last level.
**Time:** O(log²n) where n is the number of nodes · **Space:** O(1) as we only use constant extra space
**Pros:** Optimal time complexity; Takes advantage of complete binary tree properties; Doesn't visit all nodes
**Cons:** More complex implementation; Only works for complete binary trees; Requires understanding of binary tree properties
### Explanation
We can use the fact that a complete binary tree is perfect (all levels full) except possibly for the last level. We can find the height of the tree and then binary search on the last level to find the exact number of nodes.

```java
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        
        int height = getHeight(root);
        if (height == 0) return 1;
        
        int upperCount = (1 << height) - 1;  // nodes in all levels except last
        int left = 0, right = (1 << height) - 1;  // possible nodes in last level
        
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (exists(mid, height, root)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return upperCount + left + 1;
    }
    
    private int getHeight(TreeNode root) {
        int height = 0;
        while (root.left != null) {
            height++;
            root = root.left;
        }
        return height;
    }
    
    private boolean exists(int idx, int height, TreeNode root) {
        int left = 0, right = (1 << height) - 1;
        for (int i = 0; i < height; i++) {
            int mid = left + (right - left) / 2;
            if (idx <= mid) {
                root = root.left;
                right = mid;
            } else {
                root = root.right;
                left = mid + 1;
            }
        }
        return root != null;
    }
}
```
### Algorithm
1. If root is null, return 0
2. Get height of tree by following left path
3. Calculate nodes in all levels except last
4. Binary search on last level:
   - For each middle position, check if node exists
   - Adjust search range based on existence
5. Return total count

# Solutions
### CSharp

```csharp
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public int CountNodes ( TreeNode root ) { if ( root == null ) { return 0 ; } int left = depth ( root . left ); int right = depth ( root . right ); if ( left == right ) { return ( 1 << left ) + CountNodes ( root . right ); } return ( 1 << right ) + CountNodes ( root . left ); } private int depth ( TreeNode root ) { int d = 0 ; for (; root != null ; root = root . left ) { ++ d ; } return d ; } }
```

### Java

```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; * } * } */ class Solution { public int countNodes ( TreeNode root ) { if ( root == null ) { return 0 ; } int left = depth ( root . left ); int right = depth ( root . right ); if ( left == right ) { return ( 1 << left ) + countNodes ( root . right ); } return ( 1 << right ) + countNodes ( root . left ); } private int depth ( TreeNode root ) { int d = 0 ; for (; root != null ; root = root . left ) { ++ d ; } return d ; } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */ /** * @param {TreeNode} root * @return {number} */ var countNodes =
  function (root) {
    const depth = (root) => {
      let d = 0;
      for (; root; root = root.left) {
        ++d;
      }
      return d;
    };
    if (!root) {
      return 0;
    }
    const left = depth(root.left);
    const right = depth(root.right);
    if (left == right) {
      return (1 << left) + countNodes(root.right);
    }
    return (1 << right) + countNodes(root.left);
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int countNodes ( TreeNode * root ) { if ( ! root ) { return 0 ; } int left = depth ( root -> left ); int right = depth ( root -> right ); if ( left == right ) { return ( 1 << left ) + countNodes ( root -> right ); } return ( 1 << right ) + countNodes ( root -> left ); } int depth ( TreeNode * root ) { int d = 0 ; for (; root ; root = root -> left ) { ++ d ; } return d ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def countNodes ( self , root : Optional [ TreeNode ]) -> int : def depth ( root ): d = 0 while root : d += 1 root = root . left return d if root is None : return 0 left , right = depth ( root . left ), depth ( root . right ) if left == right : # left child subtree: (1<<left)-1 # plus root: +1 # so total except right subtree: (1<<left) return ( 1 << left ) + self . countNodes ( root . right ) else : # left = right+1 return ( 1 << right ) + self . countNodes ( root . left ) ############ ''' >>> 2 ** 3 8 >>> 3 ** 2 9 ''' # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution ( object ): def getHeight ( self , root ): height = 0 while root : height += 1 root = root . left return height def countNodes ( self , root ): count = 0 while root : l , r = map ( self . getHeight , ( root . left , root . right )) if l == r : count += 2 ** l root = root . right else : count += 2 ** r root = root . left return count
```