Count Complete Tree Nodes

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

Definition of a complete binary tree from Wikipedia:
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.

Solution:

Get the height of left and right tree. If the same, the total number of nodes can be calculated by 2^h - 1. If left height is not equal to right height, we recursively count right and left tree nodes.

public int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left  = getLeftHeight(root.left)   + 1,
        right = getRightHeight(root.right) + 1,
        count = 0;
    if (left == right) {
        return count = (2 << (left - 1)) - 1;
    } else {
        return count = countNodes(root.left) + countNodes(root.right) + 1;
    }
}

private int getLeftHeight(TreeNode root) {
    int count = 0;
    TreeNode current = root;
    while (current != null) {
        count++;
        current = current.left;
    }
    return count;
}

private int getRightHeight(TreeNode root) {
    int count = 0;
    TreeNode current = root;
    while (current != null) {
        count++;
        current = current.right;
    }
    return count;
}