Symmetric Binary Tree - Amazon Top Interview Questions

                        Solution in C++ :

bool solve(Tree* root) {
    if (!root) return true;
    stack<Tree*> p, q;
    p.push(root->left), q.push(root->right);
    while (!p.empty() && !q.empty()) {
        auto m = p.top(), n = q.top();
        p.pop(), q.pop();
        if (!m && !n) continue;
        else if (!m || !n) return false;
        if (m->val != n->val)
            return false;
        p.push(m->left), p.push(m->right);
        q.push(n->right), q.push(n->left);
    } 
    return p.empty() && q.empty();
}
                    

                        Solution in Java :

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */
class Solution {
    public boolean solve(Tree root) {
        return versionA(root);
        // return versionB(root);
    }

    // breadth first search, with padding for null child nodes
    // performance: 62%
    // This also works when Tree is non-bianry, i.e. more than 2 child nodes for a parent node.
    boolean versionA(Tree root) {
        if (root == null) {
            return true;
        }

        // a special NULL node
        Tree padding = new Tree();

        ArrayList<Tree> list = new ArrayList<>();
        list.add(root);

        while (!list.isEmpty()) {
            if (!isValid(list, padding)) {
                return false;
            }
            list = getNextLevel(list, padding);
        }
        return true;
    }

    // check as if we were checking palindrome: all the nodes at one level
    boolean isValid(ArrayList<Tree> list, Tree padding) {
        int head = 0;
        int tail = list.size() - 1;

        while (head < tail) {
            if (!isValid(list.get(head), list.get(tail), padding)) {
                return false;
            }
            head++;
            tail--;
        }

        return true;
    }

    boolean isValid(Tree a, Tree b, Tree padding) {
        if ((a == padding) && (b == padding)) {
            return true;
        }
        if ((a == padding) || (b == padding)) {
            return false;
        }
        // no padding
        return a.val == b.val;
    }

    // get all the nodes at next level, adding the spcial "padding" node when a child node is null.
    ArrayList<Tree> getNextLevel(ArrayList<Tree> list, Tree padding) {
        ArrayList<Tree> result = new ArrayList<>();

        for (Tree node : list) {
            if (node == padding) {
                continue;
            }
            if (node.left != null) {
                result.add(node.left);
            } else {
                result.add(padding);
            }

            if (node.right != null) {
                result.add(node.right);
            } else {
                result.add(padding);
            }
        }
        return result;
    }

    // this is how most people implemented. It is a better solution:
    // shorter code, less memory and better performance
    // performance: 85%
    boolean versionB(Tree root) {
        if (root == null) {
            return true;
        }

        return recursionB(root.left, root.right);
    }

    boolean recursionB(Tree a, Tree b) {
        if ((a == null) && (b == null)) {
            return true;
        }
        if ((a == null) || (b == null)) {
            return false;
        }
        if (a.val != b.val) {
            return false;
        }
        return recursionB(a.left, b.right) && recursionB(a.right, b.left);
    }
}
                    

                        Solution in Python : 
                            
# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, root):
        def symmetry(l, r):
            return (l is None and r is None) or bool(
                l
                and r
                and l.val == r.val
                and symmetry(l.left, r.right)
                and symmetry(l.right, r.left)
            )

        return not root or symmetry(root.left, root.right)