# A straightforward, explanatory iterative approach in C++

• ``````class Solution {
public:
//static bool balance=true;
bool isBalanced(TreeNode *root) {
// depth(root)=max(depth(left),depth(right))+1;
// if(!root) depth=0;
//depth(root);
if(!root) return true;
return depth(root);
}

int depth(TreeNode *root) { // return depth or 0 if unbalanced
vector<TreeNode *> tstn; //stack of unprocessed nodes with at least one child
bool processed=false, unbalanced=false;
TreeNode *top;
int tmp, dep;
vector<int> depstn; // stack of recently calculated unused depth
do {
if(processed) {
top=tstn.back();
if(root==top->left) {
if(top->right) { // top->left==root, top->right!=NULL
depstn.push_back(dep);
root=top->right;
processed=false;
}
else { // top->left==root, top->right==NULL. processed remain true
if(dep>1) { return 0; }
dep=2;
root=top;
tstn.pop_back();
}
}
else {
if(!top->left){ // top->left==NULL, top->right==root. processed remain true
if(dep>1) { return 0; }
dep=2;
root=top;
tstn.pop_back();
}
else { // depth(top->left) is in depstn, top->right==root. processed remain true
tmp=depstn.back(); // only here depstn was popped
if(tmp-dep>1 || tmp-dep<-1) { return 0; }
depstn.pop_back();
root=tstn.back();
tstn.pop_back();
dep=(tmp>dep)?(tmp+1):(dep+1);
}
}
}
else {
if(root->left) { // case 3, 2, root->left!=NULL
tstn.push_back(root);
root=root->left;
}
else {
if(root->right) { // case 1, root->left==NULL, root->right!=NULL
tstn.push_back(root);
root=root->right;
}
else { // case 0, root->left==NULL, root->right==NULL
dep=1;
processed=true;
}
}
}
} while(!tstn.empty()); // only nonNULL one was pushed on to stack tstn
return dep;
}
};``````

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