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.

I want to count the number of nodes in a Complete Binary tree but all I can think of is traversing the entire tree. This will be a O(n) algorithm where n is the number of nodes in the tree. what could be the most efficient algorithm to achieve this?
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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s