# C++ recursive and iterative solution O(logn^2)

• Recursive Method:

1. Check if current node is the root of a full BT. If yes, number of nodes = pow(2,height) -1.
2. Calculate number of nodes in both left and right subtrees. Return sum + 1.
``````class Solution {
public:
int countNodes(TreeNode* root) {

if(!root) return 0;
int hl = 0, hr = 0;
TreeNode *lnode = root, *rnode = root;
while(lnode){ lnode = lnode->left; hl++; }
while(rnode){ rnode = rnode->right; hr++; }
if(hl == hr) return pow(2, hl) - 1;
else return countNodes(root->left) + countNodes(root->right) + 1;

}
}
``````

Iterative Method:

Find the last node of the tree. By calculating the height of left and right subtree, we can decide the last node is in the left or right.

``````class Solution {
public:
int countNodes(TreeNode* root) {

// Iterative - Find the last node of the tree
if(!root) return 0;

int hl = leftheight(root), hr = rightheight(root), ans = 1;
int hll = hl-1, hlr = rightheight(root->left), hrl = leftheight(root->right), hrr = hr-1;

while(root->left){
// Three cases to move to the right subtree:
// Case 1: I am the root of a full BT
// Case 2: Only the left subtree is a full BT
// Case 3: Both left and right subtrees are full BTs and have same height
if((hl == hr) ||
(hll == hlr && hrl == hrr && hll == hrr) ||
(hll == hlr && hrl != hrr)){
root = root->right;
ans = ans * 2 + 1;
// cout<<"move right, ans = "<<ans<<endl;
hr = hrr; hrr = rightheight(root->right); hrl = leftheight(root->right);
hl = hrl; hll = leftheight(root->left);   hlr = rightheight(root->left);
}
// Two cases to move to the right subtree:
// Case 1: Only the right subtree is a full BT
// Case 2: Both subtrees are full BTs but have diff height
else if((hll == hlr && hrl == hrr && hll != hrr) ||
(hll != hlr && hrl == hrr)){
root = root->left;
ans = ans * 2;
hr = hlr; hrr = rightheight(root->right); hrl = leftheight(root->right);
hl = hll; hll = leftheight(root->left);   hlr = rightheight(root->left);
}
}
return ans;
}
int leftheight(TreeNode* root){
int ans = 0;
while(root){ root = root->left; ans++; }
return ans;
}
int rightheight(TreeNode* root){
int ans = 0;
while(root){ root = root->right; ans++; }
return ans;
}
};
``````

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