LC101. Symmetric Tree

Problem Description

Source: https://leetcode.com/problems/symmetric-tree/

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1, 2, 2, 3, 4, 4, 3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1, 2, 2, null, 3, null, 3] is not:

    1
   / \
  2   2
   \   \
   3    3

Solution

High level strategy

To check whether two nodes are identical, we can check the following conditions:

1. If both nodes are null, then they are the same.
2. If one of the nodes is null, then they are not the same.
3. If the value of one node is not equal to the value of the other, then they are not the same.

To check whether a tree is symmetrical, we can simply apply the logics above to the opposite nodes on each side of the tree. That is, we compare the right child of the left child with the left child of the right child, so on and so forth. We recurse down both sides of the root node, and return true if and only if both sides return true. The time complexity of this solution is O(n), where 'n' is equal to the number of nodes. The space complexity of this solution is O(logn), or O(h), where 'h' is equal to the height of the tree.

Code

Javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 **/

const isSymmetric = (root) => {
    if (root === null) return true;
    return isSame(root.left, root.right);
};

const isSame = (node1, node2) => {
    if (node1 === null && node2 === null) return true;
    if (node1 === null || node2 === null) return false;
    if (node1.val !== node2.val) return false;
    
    return isSame(node1.left, node2.right) && isSame(node1.right, node2.left);
};

Java

public boolean isSymmetric(TreeNode root) {
    return root==null || isSymmetricHelp(root.left, root.right);
}

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

Other Solutions

BFS Approach

/**
 * We can also explore each level through BFS,
 * then iterate through all nodes in each level to see if they are a mirror
 * (same idea as checking if a string is a palindrome). 
 */

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>(); 
        queue.add(root);
        while(queue.size() > 0) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            while(size > 0) {
                TreeNode cur = queue.poll();
                if (cur == null) {
                    level.add(null);
                } else {
                    level.add(cur.val);
                    queue.add(cur.left);
                    queue.add(cur.right);
                }
                size--;
            }
            List<Integer> reverse = new ArrayList<>();
            for(int i = level.size() - 1; i >= 0; i--) {
                reverse.add(level.get(i));
            }
            if (!level.equals(reverse)) return false;
        }
        return true;
    }
}