222. 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.

for complete tree, if h(l) == h(r) then then the nodes are 2^h -1;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int countNodes(TreeNode root) {

        if(root == null) return 0;
        int l = getHeight(root, true);
        int r = getHeight(root, false);

        if(l == r) return (2 <<(l-1)) -1;
        return countNodes(root.left) + countNodes(root.right) +1;

    }

    private int getHeight(TreeNode root, boolean toLeft){
        if(root ==null) return 0;
        int h = 1;
        if(toLeft){
            while(root.left != null){
                root = root.left;
                h++;
            }
        }else{
            while(root.right != null){
                root = root.right;
                h++;
            }
        }
        return h;
    }
}