Given a **Complete Binary Tree**, count the number of nodes.

__Definition of a Complete Binary Tree:__

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 **2 ^{h}** nodes inclusive at the last level

**h**. Consider the following example.

**Example:**

Input:1 / \ 2 3 / \ / 4 5 6Output:6

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. That means that a complete tree has ** 2** nodes in the

^{k}

**level if the kth level is not the last one. The last level maybe not filled completely, and hence in the last level, the number of nodes could vary from**

`kth`

**. Consider the following figures to have a better understanding.**

`1 to 2`^{k}

**Algorithm to solve this problem:**

- Get the height of the left subtree.
- Get the height of the right subtree.
- When they are equal, the number of nodes =
.`(2`

^{h}-1) - When they are not equal, recursively get the number of nodes from the left and right sub-trees. and the total number of nodes in this case is:

countNodes(root.left) + countNodes(root.right) + 1

The following figure is a pictorial representation of the recursive algorithm.

Following is the implementation of this Algorithm. First of all, we have used the `TreeNode`

for the solution.

public class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int x) { this.val = x; this.left = null; this.right = null; } }

Count the number of nodes in a complete binary tree by `CompleteBinaryTree.java`

```
public class CompleteBinaryTree {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int lh = getLeftHeight(root);
int rh = getRightHeight(root);
if (lh == rh) {
int count = (int) Math.pow(2, lh) - 1;
return count;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
private int getLeftHeight(TreeNode node) {
if (node == null) {
return 0;
}
int height = 0;
while (node != null) {
height++;
node = node.left;
}
return height;
}
private int getRightHeight(TreeNode node) {
if (node == null) {
return 0;
}
int height = 0;
while (node != null) {
height++;
node = node.right;
}
return height;
}
}
```

Time Complexity: ** O(n)** where n is the number of nodes of the Tree.

Categories: Binary Tree