Symmetric Tree

Problem

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• -100 <= Node.val <= 100

Follow up: Could you solve it both recursively and iteratively?

Solution

This one sounds pretty hard. My first instinct is to transform the tree into some flat structure, e.g. a string, and then do a string comparison.

Alternatively, we could use something like a Stack. Push the nodes on the left side, pop them on the right side. A stack solution can be implemented both iteratively and recursively, which meets the follow-up question.

Approach 1

Two stacks.

Go through the left and right side of the tree. Push the contents of the tree in a stack. Then empty both stacks checking that popped nodes are equal, and that stacks are both empty at the end.

Notes:

• O(n) runtime, O(n) space
• You’d need to reverse the order on the right side, e.g. pre-order for the left side, post-order for the right side
• You’d need to insert null nodes (e.g. a lack of children)

While implementing the above, I realized maintaining a stack is more work than just doing recursion. Here’s a very simple solution:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isSymmetric(root.left, root.right);
    }

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