# Faster than the most voted Java solution

• Get the depth of the left sub-tree 'l' and the depth of fully filled level in the right sub-tree 'r'.

• If they are the same, the tree is fully filled.
• Otherwise, get the depth of fully filled level in the left tree h. If the left subtree is not filled, check left sub-tree. But be reminded here that the right sub-tree is filled to the previous level. Also, note that the 'l' and 'r' value of the left sub-tree are 'l-1' and 'r-1' now.
• The case for the left sub-tree is fully filled is similarly handled, but the 'l' value is unknown.
``````    public int countNodes(TreeNode root) {
return countNodes(root, 0, 0);
}
public int countNodes(TreeNode root, int l, int r) {
if (root == null) {
return 0;
}
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 (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
return (1<<r) + countNodes(root.left, l-1, h-1);
} else {
return (1<<l) + countNodes(root.right, 0, r-1);
}
}
``````

• 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;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.