I see some solutions are counting and compare the height of both left and right sub-trees. We actually only need to count the height of the right sub-tree, which can be either height-1 or height-2, then we know which sub-tree is the perfect BST, and which side to go next.

```
public int CountNodes(TreeNode root) {
int depth;
int cntNodes=0;
if (root == null) return 0;
depth = TreeDepth(root);
if (depth == 1) return 1;
while (root != null)
{
if (TreeDepth(root.right) < depth - 1)
{
root = root.left;
cntNodes += 1 << (depth - 1);
}
else
{
root = root.right;
cntNodes += 1 << (depth - 2);
}
depth--;
}
return cntNodes;
}
public int TreeDepth(TreeNode root)
{
int depth = 0;
while (root != null)
{
depth++;
root = root.left;
}
return depth;
}
```