:orphan:

Subtree of Another Tree
=======================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/subtree-of-another-tree/

Given the roots of two binary trees ``root`` and ``subRoot``, return
``true`` if there is a subtree of ``root`` with the same structure and
node values of\ ``subRoot`` and ``false`` otherwise.

A subtree of a binary tree ``tree`` is a tree that consists of a node in
``tree`` and all of this node's descendants. The tree ``tree`` could
also be considered as a subtree of itself.

**Example 1:**

|image1|

::

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

**Example 2:**

|image2|

::

   Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
   Output: false

**Constraints:**

- The number of nodes in the ``root`` tree is in the range
  ``[1, 2000]``.
- The number of nodes in the ``subRoot`` tree is in the range
  ``[1, 1000]``.
- ``-10``\ :sup:```4```\ ``<= root.val <= 10``\ :sup:```4```
- ``-10``\ :sup:```4```\ ``<= subRoot.val <= 10``\ :sup:```4```

.. |image1| image:: https://assets.leetcode.com/uploads/2021/04/28/subtree1-tree.jpg
.. |image2| image:: https://assets.leetcode.com/uploads/2021/04/28/subtree2-tree.jpg

.. highlight:: python

Pattern
-------
Tree, Depth-First Search, String Matching, Binary Tree, Hash Function

Approaches
----------

.. tab-set::

    .. tab-item:: DFS

        **Code**

        .. literalinclude:: ../problems/easy/subtree-of-another-tree/subtree_of_another_tree__dfs.py
            :language: python
            :lines: 10-

        **Test**

        >>> from subtree_of_another_tree__dfs import TreeNode, isSubtree
        >>> isSubtree(TreeNode.from_list([3, 4, 5, 1, 2]), TreeNode.from_list([4, 1, 2]))
        True
        >>> root = TreeNode.from_list([3, 4, 5, 1, 2, None, None, None, None, 0])
        >>> isSubtree(root, TreeNode.from_list([4, 1, 2]))
        False

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

        .. autofunction:: subtree_of_another_tree__dfs.isSubtree