:orphan:

Symmetric Tree
==============

.. highlight:: none

Problem
-------
https://leetcode.com/problems/symmetric-tree/

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

 

**Example 1:**

|image1|

::


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

**Example 2:**

|image2|

::


   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?

.. |image1| image:: https://assets.leetcode.com/uploads/2021/02/19/symtree1.jpg
.. |image2| image:: https://assets.leetcode.com/uploads/2021/02/19/symtree2.jpg

.. highlight:: python

Pattern
-------
Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution
--------
Starting at the root, observe that it does not affect the symmetry of the tree.
Only the left and right subtrees with roots ``left = root.left`` and
``right = root.right`` do. We need to check if the left subtree is a mirror
image of the right. This is true if and only if ``left.val == right.val`` and
the subtree of``left.left`` is a mirror image of ``right.right`` and the
subtree of ``left.right`` is a mirror image of ``right.left``. Checking whether
the further subtrees are mirror images of each other can be solved using
recursion, until both children are ``null``. ::

                         root
               /                    \\
            left-                   right-
        /         \\             /          \\
    left.left+ left.right* right.left+ right.right*

The - nodes should be equal in value, while the + subtrees, and * subtrees should be
mirror images.

Code
----

.. literalinclude:: ../problems/easy/symmetric-tree/symmetric_tree__approach_1.py
    :language: python
    :lines: 14-

Test
----
>>> from symmetric_tree__approach_1 import TreeNode, isSymmetric
>>> root = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3)))
>>> isSymmetric(root)
True
>>> root = TreeNode(1, TreeNode(2, None, TreeNode(2)), TreeNode(2, None, TreeNode(2)))
>>> isSymmetric(root)
False

Complexity
----------
| :math:`n` is the number of nodes in the tree
| Time: :math:`O(n)` — visit each node once
| Auxiliary Space: :math:`O(1)`

.. autoclass:: symmetric_tree__approach_1.TreeNode
   :members:
   :show-inheritance:
   :undoc-members:

.. autofunction:: symmetric_tree__approach_1.isSymmetric

.. autofunction:: symmetric_tree__approach_1.check_subtrees