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

Based on the definition of  complete tree, we know that if the left most root to leaf path has the same count as the right most root to leaf path, then the tree is fully filled. Thus we can calculate the tree number using  2^height - 1. If counts don't equal to each other, we recursively calculate left tree and right tree.

public int countNodes(TreeNode root) {
        if (root == null)
            return 0;
        int left = countLeft(root);
        int right = countRight(root);
        if (left == right)
            return (2 << (left - 1)) - 1;
        else
            return countNodes(root.left) + countNodes(root.right) + 1;
    }
    
    private int countLeft(TreeNode root) {
        int count = 0;
        while(root != null) {
            root = root.left;
            count++;
        }
        return count;
    }
    
    private int countRight(TreeNode root) {
        int count = 0;
        while(root != null) {
            root = root.right;
            count++;
        }
        return count;
    }