# Count Complete Tree Nodes

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 2h nodes inclusive at the last level h. Consider the following example.

Example:

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

Output: 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 `2k` nodes in the `kth` 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 `1 to 2k`. Consider the following figures to have a better understanding. The last level maybe not filled completely, and hence in the last level, the number of nodes could vary from 1 to 2k.

Algorithm to solve this problem:

1. Get the height of the left subtree.
2. Get the height of the right subtree.
3. When they are equal, the number of nodes = `(2h -1)`.
4. 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