SymmetricTree.java

import java.util.Stack;
import java.util.LinkedList;

public class SymmetricTree {
    public boolean isSymmetricQueue(TreeNode root) {
        if (root == null) return true; // if you say so
        
        // initialize a queue since we are going to use breadth first traverse
        LinkedList<TreeNode> q = new LinkedList<TreeNode>();
        if (root.left !=null && root.right != null) {
            q.add(root.left);
            q.add(root.right);
        }else{
            if (root.left != null && root.right == null) return false;
            if (root.left == null && root.right != null) return false; // not symmetric on the first level already.
        }
        
        while(q.isEmpty() != true){
            // dequeue the first two
            TreeNode n1 = q.remove();
            TreeNode n2 = q.remove();
            
            if(n1.val != n2.val) return false;
            else{
                if (n1.left !=null && n2.right !=null){
                    q.add(n1.left);
                    q.add(n2.right);
                }
                
                if (n1.right !=null && n2.left !=null){
                    q.add(n1.right);
                    q.add(n2.left);
                }
                
                if (n1.left != null && n2.right == null) return false;
                if (n1.left == null && n2.right != null) return false;
                if (n1.right != null && n2.left == null) return false;
                if (n1.right == null && n2.left != null) return false;
            }
        }
        return true;
    }
    
    public boolean isSymmetricStack(TreeNode root) {
        if (root == null) return true;
        Stack<TreeNode> left = new Stack<TreeNode>();
        Stack<TreeNode> right = new Stack<TreeNode>();
        
        if(root.left == null && root.right == null) return true;
        if(root.left != null && root.right == null) return false;
        if(root.left == null && root.right != null) return false;
        
        
        dfsLeft(root.left, left);
        dfsRight(root.right, right);
        
        
        if (left.size() != right.size()) return false;
        TreeNode nodeLeft = null;
        TreeNode nodeRight = null;
        while(left.isEmpty() != true){
            nodeLeft = left.pop();
            nodeRight = right.pop();
            if (nodeLeft == null && nodeRight != null) return false;
            if (nodeLeft != null && nodeRight == null) return false;
            if (nodeLeft != null && nodeRight != null){
                if (nodeLeft.val != nodeRight.val) return false;
            }
        }
        return true;
    }
    
    private void dfsLeft(TreeNode root, Stack<TreeNode> left){
        left.push(root);
        if (root.left != null) dfsLeft(root.left, left);
        else left.push(null); // we must push null to the stack to reflect difference!
        
        if (root.right != null) dfsLeft(root.right, left);
        else left.push(null);
    }
    
    private void dfsRight(TreeNode root, Stack<TreeNode> right){
        right.push(root);
        if (root.right != null) dfsRight(root.right, right);
        else right.push(null);
        
        if (root.left != null) dfsRight(root.left, right);
        else right.push(null);
    }
}