Symmetric Tree

Problem

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

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

Constraints

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

Solution

The problem Symmetric Tree can be solved recursively and iteratively. First, a recursive solution uses the same technique as Same Tree to compare left and right trees of root node. However, as the goal is to check if they are symmetrical, instead of moving in the same direction, it moves in the opposite direction to check if the nodes have the same value. Next, in an iterative solution, left tree is traversed using a preorder traversal and the right tree postorder traversal. If two trees are symmetrical, results should be the reversal of each other. One thing to note is that a postorder traversal contains a process of reversing the result in the end. Time complexity could be improved by leaving it out and checking if both results are the same instead of checking if they are reversal of each other.

Implementation (Recursive)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
  public:
    bool isSymmetricTree(TreeNode *left, TreeNode *right)
    {
        if (left == NULL || right == NULL)
            return left == right;

        return left->val == right->val && isSymmetricTree(left->left, right->right) && isSymmetricTree(left->right, right->left);
    }

    bool isSymmetric(TreeNode *root) { return isSymmetricTree(root->left, root->right); }
};

Implementation (Iterative)

typedef stack<TreeNode *> Stack;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
  public:
    void traverseTree(vector<TreeNode *> &nodes, TreeNode *root, bool pre_order)
    {
        Stack roots;
        roots.push(root);

        while (!roots.empty())
        {
            root = roots.top();
            roots.pop();
            nodes.push_back(root);

            if (root != NULL)
            {
                if (pre_order)
                {
                    roots.push(root->right);
                    roots.push(root->left);
                }
                else
                {
                    roots.push(root->left);
                    roots.push(root->right);
                }
            }
        }

        // if (!pre_order)
        //    reverse(nodes.begin(), nodes.end());
    }
    bool isSymmetric(TreeNode *root)
    {
        vector<TreeNode *> lnodes, rnodes;
        traverseTree(lnodes, root->left, true);
        traverseTree(rnodes, root->right, false);

        if (lnodes.size() != rnodes.size())
            return false;

        // reverse(rnodes.begin(), rnodes.end());
        for (int i = 0; i < lnodes.size(); i++)
        {
            if (lnodes[i] == rnodes[i])
                continue;
            else if (lnodes[i] == NULL || rnodes[i] == NULL || lnodes[i]->val != rnodes[i]->val)
                return false;
        }

        return true;
    }
};