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.


Comment