#include <iostream>
using namespace std;
class Node{
public:
int data;
Node *left, *right;
Node(int data){
this->data = data;
this->left = this->right = NULL;
}
};
int leftHeight(Node* node){
int h=0;
while(node){
h++;
node = node->left;
}
return h;
}
int rightHeight(Node* node){
int h=0;
while(node){
h++;
node = node->right;
}
return h;
}
int countNodes(Node* root){
if(!root)
return 0;
int lh = leftHeight(root);
int rh = rightHeight(root);
if(lh==rh)
return (1<<lh)-1;
return countNodes(root->left)+countNodes(root->right)+1;
}
int main() {
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
root->left->left->left = new Node(8);
root->left->left->right = new Node(9);
root->left->right->left = new Node(10);
cout<<countNodes(root)<<endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2xhc3MgTm9kZXsKCXB1YmxpYzoKCWludCBkYXRhOwoJTm9kZSAqbGVmdCwgKnJpZ2h0OwoJTm9kZShpbnQgZGF0YSl7CgkJdGhpcy0+ZGF0YSA9IGRhdGE7CgkJdGhpcy0+bGVmdCA9IHRoaXMtPnJpZ2h0ID0gTlVMTDsKCX0KfTsKCmludCBsZWZ0SGVpZ2h0KE5vZGUqIG5vZGUpewoJaW50IGg9MDsKCXdoaWxlKG5vZGUpewoJCWgrKzsKCQlub2RlID0gbm9kZS0+bGVmdDsKCX0KCXJldHVybiBoOwp9CgppbnQgcmlnaHRIZWlnaHQoTm9kZSogbm9kZSl7CglpbnQgaD0wOwoJd2hpbGUobm9kZSl7CgkJaCsrOwoJCW5vZGUgPSBub2RlLT5yaWdodDsKCX0KCXJldHVybiBoOwp9CgppbnQgY291bnROb2RlcyhOb2RlKiByb290KXsKCWlmKCFyb290KQoJCXJldHVybiAwOwoJaW50IGxoID0gbGVmdEhlaWdodChyb290KTsKCWludCByaCA9IHJpZ2h0SGVpZ2h0KHJvb3QpOwoJaWYobGg9PXJoKQoJCXJldHVybiAoMTw8bGgpLTE7CglyZXR1cm4gY291bnROb2Rlcyhyb290LT5sZWZ0KStjb3VudE5vZGVzKHJvb3QtPnJpZ2h0KSsxOwp9CgoKaW50IG1haW4oKSB7CglOb2RlKiByb290ID0gbmV3IE5vZGUoMSk7Cglyb290LT5sZWZ0ID0gbmV3IE5vZGUoMik7Cglyb290LT5yaWdodCA9IG5ldyBOb2RlKDMpOwoJcm9vdC0+bGVmdC0+bGVmdCA9IG5ldyBOb2RlKDQpOwoJcm9vdC0+bGVmdC0+cmlnaHQgPSBuZXcgTm9kZSg1KTsKCXJvb3QtPnJpZ2h0LT5sZWZ0ID0gbmV3IE5vZGUoNik7Cglyb290LT5yaWdodC0+cmlnaHQgPSBuZXcgTm9kZSg3KTsKCXJvb3QtPmxlZnQtPmxlZnQtPmxlZnQgPSBuZXcgTm9kZSg4KTsKCXJvb3QtPmxlZnQtPmxlZnQtPnJpZ2h0ID0gbmV3IE5vZGUoOSk7Cglyb290LT5sZWZ0LT5yaWdodC0+bGVmdCA9IG5ldyBOb2RlKDEwKTsKCWNvdXQ8PGNvdW50Tm9kZXMocm9vdCk8PGVuZGw7CglyZXR1cm4gMDsKfQ==