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.

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   public int countNodes(TreeNode root) {
  12.     if (root == null)
  13.       return 0;
  15.     int hLeft = getHeight(root.left);
  16.     int hRight = getHeight(root.right);
  18.     if (hLeft == hRight)
  19.       return (1 << hLeft) + countNodes(root.right);
  20.     else
  21.       return (1 << hRight) + countNodes(root.left);
  22.   }
  24.   int getHeight(TreeNode root) {
  25.     if (root == null)
  26.       return 0;
  28.     return 1 + getHeight(root.left);
  29.   }
  30. }