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#

/**
* 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);
};

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;
}
}