# 9ms iterative C++ solution

• First I'd like to present my 16ms recursive solution:

``````{
if (!root) {
height=0;
return true;
}
int left, right;
bool ans= (isBalanced(root->left, left)&&isBalanced(root->right, right)&&(left-right>0?left-right:right-left)<=1);
height=1+max(right, left);
printf("val=%d left=%d right=%d\n", root->val, left, right);
return ans;
}
bool isBalanced(TreeNode* root) {
int height;
return isBalanced(root, height);
}

I won't bother explain it as it is quite straight foward, then I convert it to an iterative solution using stack, and the time comes down to
9ms:

```struct Frame{
int left, right;
int & height;
TreeNode* root;
unsigned char status;
Frame(TreeNode* root, int & height):root(root),height(height),status(0){}
};
bool isBalanced(TreeNode* root) {
stack<Frame> s;
int height;
bool ret=true;
s.push(Frame(root, height));
while (s.size()) {
Frame & f=s.top();
//if (f.root) {
//    printf("entering frame %d.\n", f.root->val);
//}
if (!f.status) {
if (!f.root) {
f.height=0;
ret=true;
s.pop();
continue;
}
f.status=1;
s.push(Frame(f.root->left, f.left));
}
else if (f.status==1) {
if (!ret) {
break;
}
f.status=2;
s.push(Frame(f.root->right, f.right));
}
else {
if (!ret||(f.left-f.right>0?f.left-f.right:f.right-f.left)>1) {
ret=false;
break;
}
f.height=1+max(f.right, f.left);
ret=true;
s.pop();
}
}
return ret;
}

As you can see the main performance gain in iterative solution is once it reached an unbalanced subtree it can immediately jumps out of the entire iteration and return!``````

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