Reference: LeetCode EPI 9.2
Difficulty: Easy

My Post: [isMirror] DFS (Recursion, One/Two Stacks) + BFS (Queue) Solution in Java

Problem

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

Example:

[1,2,2,3,4,4,3] is symmetric:

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

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

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

Follow up: Bonus points if you could solve it both recursively and iteratively.

Analysis

Idea: A tree is symmetric if it is a mirror reflection of itself.

Note: Distinguish the concept of symmetric (one tree) and mirror reflection (two trees).

1
2
3
4
5
6
7
8
9
    1
   / \
  2   2       t1 & t2
 / \ / \
3  4 4  3
|  | |  |
---|-|----->  isMirror(t1.left, t2.right)
   | |      
   -------->  isMirror(t1.right, t2.left)

The question is when are two trees a mirror reflection of each other? Three conditions:

  • Their two roots have the same value.
  • The right subtree t1.right of each tree t1 is a mirror reflection of the left subtree t2.left of the other tree t2.
  • The left subtree t1.left of each tree t1 is a mirror reflection of the right subtree t2.right of the other tree t2.

Bad Idea (the wrong direction):

A tree is symmetric if its left subtree is symmetric and its right subtree is symmetric. Consider this case:

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

Two subtrees of root are not symmetric, but the root is symmetric.

From EPI, swapping any subtrees of a tree and comparing with the original is also workable.

Recursion

Come up with the recursive structure.

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isSymmetric(TreeNode root) {
  return isMirror(root, root);
}

private boolean isMirror(TreeNode t1, TreeNode t2) {
  // base case
  if (t1 == null && t2 == null) return true;
  if (t1 == null || t2 == null) return false;
  // check values
  if (t1.val != t2.val) return false;
  // check left subtree and right subtree
  return isMirror(t1.right, t2.left) && isMirror(t1.left, t2.right);
}

Improvement:

Actually, there is not too much improvement since it is bounded by a constant $2$.

1
2
3
4
5
6
public boolean isSymmetric(TreeNode root) {
  if (root == null) { // required
    return true;
  }
  return isMirror(root.left, root.right); // so t1 and t2 are different trees
}

Time: $O(N)$ because we traverse the entire input tree once ($\sim 2N$).
Space: $O(h)$

Iteration (One/Two Stacks)

Use two stacks to simulate the recursive method.

Note: Null check => Value check

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean isSymmetric(TreeNode root) {
  if (root == null) { // need checking because we use root's value
    return true;
  }
  Stack<TreeNode> lStack = new Stack<>();
  Stack<TreeNode> rStack = new Stack<>();
  // Preorder-like traversal
  lStack.push(root.left); rStack.push(root.right);
  
  while (lStack.size() > 0 && rStack.size() > 0)  {
    TreeNode t1 = lStack.pop();
    TreeNode t2 = rStack.pop();
    // null check
    if (t1 == null && t2 == null) continue;
    if (t1 == null || t2 == null) return false;
    // value check
    if (t1.val != t2.val) return false;
    // push children
    lStack.push(t1.right); lStack.push(t1.left); // could be null
    rStack.push(t2.left);  rStack.push(t2.right);
  }
  // One of the stack might be empty
  return lStack.size() == 0 && rStack.size() == 0;
}

Or just use one stack:

  • Be careful of the ordering of pushing.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public boolean isSymmetric(TreeNode root) {
  if (root == null) {
    return true;
  }
  if (root.left == null && root.right == null) return true;
  if (root.left == null || root.right == null) return false;
  // children are not null
  Stack<TreeNode> stack = new Stack<>();
  stack.push(root.left);
  stack.push(root.right);
  
  while (stack.size() > 0) {
    TreeNode t1 = stack.pop();
    TreeNode t2 = stack.pop();
    // null check
    if (t1 == null && t2 == null) continue;
    if (t1 == null || t2 == null) return false;
    // value check
    if (t1.val != t2.val) return false;
    // push children
    stack.push(t1.right); stack.push(t2.left); // could be null
    stack.push(t1.left); stack.push(t2.right);
  }
  
  return true;
}

Time: $O(N)$
Space: $O(h)$

Iteration (BFS)

Compare nodes at each layer.

  • Each two consecutive nodes in the queue should be equal.
  • Each time, two nodes are extracted and their values are compared.
  • Then their right and left children of the two nodes are enqueued in opposite order.
1
2
3
4
5
6
    1
   / \
  2   2     queue: 2    2 (t1)
 / \ / \
3  4 4  3   queue: 4    4    3    3
                           t2.r t1.l
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean isSymmetric(TreeNode root) {
  if (root == null) {
    return true;
  }
  Queue<TreeNode> queue = new LinkedList<>();
  queue.offer(root.left);
  queue.offer(root.right);

  while (queue.size() > 0) {
    TreeNode t1 = queue.poll();
    TreeNode t2 = queue.poll();
    // check
    if (t1 == null && t2 == null) continue;
    if (t1 == null || t2 == null) return false;
    if (t1.val != t2.val) return false;
    // offer children
    queue.offer(t1.left);
    queue.offer(t2.right);

    queue.offer(t1.right);
    queue.offer(t2.left);
  }
  return true;
}

Time: $O(N)$
Space: $O(w)$ where $w$ is the maximum number nodes in a level of the tree.