# Symmetric Tree

• Can we do it with DFS? I think it is the same as the second solution other than the fact that DFS uses stacks.
To be more specific, have two pointers(or stacks) traverse down left and right children. One will do post-order-traversal on the left and the other will do pre-order-traversal.

• You mean doing DFS iteratively? Yes. Just change the queue to a stack and it will do DFS.

• Can we do it with DFS? I think it is the same as the second solution other than the fact that DFS uses stacks.

• I think in the first recursive solution, it traverses the entire tree twice, if you call mirror function in this way: isMirror(root, root);

• Even in iterative case,i think it will traverse the tree twice.

• The avoid traverse the tree twice in the first recursive solution, just use following in isSymmetric:
if (root == null)
return true;
return dfs(root.left, root.right);

• I think preorder traversal can also solve it,but why I can not pass when input is [1]?My IDEA print "true" but oj print "false"

• The second iterative solution do unnecessary push and pop twice since first push(root) twice.
Here can just push(root->left) & posh(root->right) to avoid this, however, we need add extra judgement of whether root is NULL first

• Another approach is to take a preorder and postorder traversal of the tree and compare the lists returned by each. If equal then true, else false.

• Inorder traversal of val, level should be symmetric.

• if inorder traversal is done then for some base cases, it is showing error

• Traverse the tree with 2 pointers, one traverses to the left first, the other one traverses to the right first, and compare the two along the way,
if there is any mismatch (value or pointer) the tree is not symmetric.

• About the space complexity: can you provide an example which explicitly shows the worse case complexity of O(n) in both approaches. For the recursive approach, I do not think that a linear tree will result in O(n) space complexity, because code with stop at the first level.

• Even in the implementations that permit it, null should not be inserted into a Queue, as null is also used as a special return value by the poll method to indicate that the queue contains no elements.
https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html

• ``````bool isSymmetric(TreeNode* root) {
if(root == NULL){
return true;
}
queue<TreeNode*> lq;
queue<TreeNode*> rq;
if(root->left){
lq.push(root->left);
}
if(root->right){
rq.push(root->right);
}
while(lq.size() && rq.size()){
TreeNode *l = lq.front();
TreeNode *r = rq.front();
lq.pop();
rq.pop();

if(l->val != r->val)
return false;
if(l->left && r->right){
lq.push(l->left);
rq.push(r->right);
}else if(!l->left && !r->right){

}else{
return false;
}
if(l->right && r->left){
lq.push(l->right);
rq.push(r->left);
}else if(!l->right && !r->left){

}else{
return false;
}

}
if(lq.size() != rq.size()){
return false;
}
return true;

}``````

• class Solution {
public boolean isSymmetric(TreeNode root) {
if (root==null) {
return true;
} else {
return isSymmetricInside(root.left, root.right);
}
}

``````public boolean isSymmetricInside(TreeNode p, TreeNode q) {
if (p==null && q==null) {
return true;
}
if (p!=null && q!=null) {
return p.val==q.val && isSymmetricInside(p.left, q.right) && isSymmetricInside(p.right, q.left);
}
return false;
}
``````

}

• In the iterative solution,

Root got added twice. Later, both its left and right got added twice. This is extra work. We can just add root.left and root.right before entering the while loop.

• class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root == nullptr)
{
return true;
}

``````    vector<int> leftTree;
vector<int> rightTree;

PreOrderTraversal(root->left, leftTree);
ReversePreOrderTraversal(root->right, rightTree);

int leftTreeSize = leftTree.size();

if (leftTreeSize != rightTree.size())
{
return false;
}

for (int i = 0; i < leftTreeSize; ++i)
{
if (leftTree.at(i) != rightTree.at(i))
{
return false;
}
}

return true;
}

void PreOrderTraversal(TreeNode* node, vector<int>& vec)
{
if (node == nullptr)
{
vec.push_back(NULL);
return;
}

vec.push_back(node->val);

PreOrderTraversal(node->left, vec);

PreOrderTraversal(node->right, vec);

return;
}

void ReversePreOrderTraversal(TreeNode* node, vector<int>& vec)
{
if (node == nullptr)
{
vec.push_back(NULL);
return;
}

vec.push_back(node->val);

ReversePreOrderTraversal(node->right, vec);

ReversePreOrderTraversal(node->left, vec);

return;
}
``````

};

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