# Recursive and iterative (DFS and BFS) in C++. Easy to understand.

• Iterative in BFS:

``````bool isSymmetric(TreeNode* root) {
if(!root) return true;
queue<nodepair> q;
q.push(make_pair(root->left, root->right));
while(!q.empty()){
nodepair p = q.front();
q.pop();
if(!p.first && !p.second) continue;
if(!p.first || !p.second) return false;
if(p.first->val != p.second->val) return false;
q.push(make_pair(p.first->left, p.second->right));
q.push(make_pair(p.first->right, p.second->left));
}
return true;
}
``````

Iterative in DFS:

``````bool isSymmetric(TreeNode* root) {
if(!root) return true;
stack<TreeNode*> sl, sr;
sl.push(root);
sr.push(root);
TreeNode * lp = root->left, *rp = root->right;
while(lp || ! sl.empty() || rp || !sl.empty()){
if((!lp && rp) || (lp && !rp)) return false;
if(lp && rp){
if(lp->val != rp->val) return false;
sl.push(lp);
sr.push(rp);
lp = lp->left;
rp = rp->right;
}else{
lp = sl.top()->right;
rp = sr.top()->left;
sl.pop();
sr.pop();
}
}
return true;
}
``````

Recursive:

``````bool isSymmetric(TreeNode* root) {
if(!root) return true;
return helper(root->left, root->right);
}
bool helper(TreeNode* left, TreeNode* right){
if(!left && !right) return true;
if(!left || !right) return false;
return (left->val == right->val) && helper(left->left, right->right) && helper(left->right, right->left);
}``````

• Thanks for sharing! I rewrote your code in Java :)

Iterative BFS:

``````private class Pair {
TreeNode left;
TreeNode right;

Pair(TreeNode left, TreeNode right) {
this.left = left;
this.right = right;
}
}

public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
queue.offer(new Pair(root.left, root.right));
while (!queue.isEmpty()) {
Pair current = queue.poll();
TreeNode left = current.left;
TreeNode right = current.right;
if (left == null && right == null) {
continue;
}
if (left == null || right == null) {
return false;
}
if (left.val != right.val) {
return false;
}
queue.offer(new Pair(left.left, right.right));
queue.offer(new Pair(left.right, right.left));
}
return true;
}
``````

Iterative DFS:

``````public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
Stack<TreeNode> leftStack = new Stack<>();
Stack<TreeNode> rightStack = new Stack<>();
TreeNode left = root.left;
TreeNode right = root.right;
while (left != null || right != null || !leftStack.isEmpty() || !leftStack.isEmpty()) {
if (left == null && right != null) {
return false;
}
if (left != null && right == null) {
return false;
}
if (left != null && right != null) {
if (left.val != right.val) {
return false;
}
leftStack.push(left);
rightStack.push(right);
left = left.left;
right = right.right;
} else {
left = leftStack.pop().right;
right = rightStack.pop().left;
}
}
return true;
}
``````

Recursive:

``````public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isSymmetric(root.left, root.right);
}

private boolean isSymmetric(TreeNode root1, TreeNode root2) {
if (root1 == null || root2 == null) {
return root1 == null && root2 == null;
}
if (root1.val != root2.val) {
return false;
}
return isSymmetric(root1.left, root2.right) && isSymmetric(root1.right, root2.left);
}``````

• This post is deleted!

• private class Pair {
TreeNode left;
TreeNode right;

``````Pair(TreeNode left, TreeNode right) {
this.left = left;
this.right = right;
}
``````

}

If we directly run your code on leetcode, it gives an error that nodepair does not exist. I have been running into this problem a lot of times doing c++ here in leetcode, make_pair() function does not work. Is there any thing I should define up on top before using the make_pair() functions?

• ``````bool isSymmetric(TreeNode* root) {
if(!root) return true;
queue<TreeNode*> q;
TreeNode* tmp;
tmp->left=root->left;
tmp->right=root->right;
q.push(tmp);

while(!q.empty()){
TreeNode* p = q.front();
q.pop();
if(p->left!=NULL && p->right!=NULL) continue;
if(p->left!=NULL || p->right!=NULL) return false;
if(p->left->val != p->right->val) return false;
TreeNode* tmp1;
tmp1->left=p->left->left;
tmp1->right=p->right->right;
q.push(tmp1);
TreeNode* tmp2;
tmp2->left=p->left->right;
tmp2->right=p->right->left;
q.push(tmp2);
}
return true;
}
``````

Even if I changed the code to this way, it still gives me compile error. So what should be the right way of applying the idea in C++?

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