Attach a non-recursive version for your reference.

public int countNodes(TreeNode root) { if (root == null) { return 0; } int l = 0, r = 0; int res = 0; while (root != null) { TreeNode node = root; if (l == 0) { while (node.left != null) { l++; node = node.left; } } node = root; if (r == 0) { while (node.right != null) { r++; node = node.right; } } if (l == r) { return res + (1 << l+1) - 1; } int h = 1; node = root.left; while (node.right != null) { h++; node = node.right; } if (h == r) {// left subtree is not full res += (1 << r); l = l-1; r = h-1; root = root.left; } else { res += (1 << l); l = 0; r = r - 1; root = root.right; } } return res; }