# [Leetcode #572.](https://leetcode.com/problems/subtree-of-another-tree/) Subtree of Another Tree

###### tags:`Binary tree` `Easy`

## Problem

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.

### Sample Input/Output

**Example 1**

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

**Example 2**

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

<br>

:::spoiler **Optimal Space & Time Complexity**

Time O(MN) | Space O(M+N) -  where M is the number of nodes in the subRoot, where N is the number of nodes in the tree

:::

<hr/>

## Solutions

### Official

**Recursive**

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:

        # Check for all subtree rooted at all nodes of tree "root"
        def dfs(node):

            # If this node is Empty, then no tree is rooted at this Node
            # Thus "tree rooted at node" cannot be same as "rooted at subRoot"
            # "tree rooted at subRoot" will always be non-empty (constraints)
            if node is None:
                return False

            # If "tree rooted at node" is identical to "tree at subRoot"
            elif is_identical(node, subRoot):
                return True

            # If "tree rooted at node" was not identical.
            # Check for tree rooted at children
            return dfs(node.left) or dfs(node.right)

        def is_identical(node1, node2):

            # If any one Node is Empty, both should be Empty
            if node1 is None or node2 is None:
                return node1 is None and node2 is None

            # Both Nodes Value should be Equal
            # And their respective left and right subtree should be identical
            return (node1.val == node2.val and
                    is_identical(node1.left, node2.left) and
                    is_identical(node1.right, node2.right))

        # Check for node rooted at "root"
        return dfs(root)

- Time complexity: `O(MN)`
For every **N** `node` in the tree, we check if the tree rooted at `node` is identical to `subRoot`. This check takes `O(M)` time, where **M** is the number of nodes in `subRoot`. Hence, the overall time complexity is `O(MN)`.

- Space complexity: `O(M+N)`
There will be at most **N** recursive call to `dfs` ( or `isSubtree`). Now, each of these calls will have **M** recursive calls to `isIdentical`. Before calling `isIdentical`, our call stack has at most `O(N)` elements and might increase to `O(N+M)` during the call. After calling `isIdentical`, it will be back to at most `O(N)` since all elements made by `isIdentical` are popped out. Hence, the maximum number of elements in the call stack will be **M+N**.

<br>

---

### Everyone's

**Recursive**

:::spoiler 月

// Time: O(t+s) || Space: O(t+s)
// t, s are each the number of nodes.
 const isSubtree = (root, subRoot) => {
    if(!subRoot) return true;
    if(!root) return false;
    if(root.val === subRoot.val){
        if(isSameTree(root,subRoot)) return true;
    }
    return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot)
    };
const isSameTree = (root, subRoot) => {
    if(!root && !subRoot) return true;
    if(!root || !subRoot) return false;
    if(root.val !== subRoot.val) return false;
    return isSameTree(root.left, subRoot.left) && isSameTree(root.right, subRoot.right)
}

:::

<br>

:::spoiler 東

/* Time O(m * n) | Space(log(m)+log(n)) 
   m is the number of root node
   n is the number of subroot node
*/ 
var isSubtree = function(root, subRoot) {
    if(!subRoot) return true;
    if(!root) return false;
    if(isSameTree(root, subRoot)) return true;
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
};

const isSameTree = function(p, q) {
    if(!p && !q) return true;
    else if(!p || !q) return false;
    else if(p.val === q.val){
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    return false;
};

:::

<br>

:::spoiler YC

/*
    time: O(m*n) - where n is the number of nodes in the tree, m is the number of nodes in the subRoot.
    space: O(m+n); - where m is the number of nodes in root, where n is the number of nodes in subRoot
*/

var isSubtree = function(root, subRoot) {
  if(!root){
    return false;
  }
  
  if(isSame(root, subRoot)){
    return true;
  }
  
  return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
  
};

function isSame(root, subRoot){
  if(!root || !subRoot){
    return !root && !subRoot;
  }
  
  if(root.val !== subRoot.val) {
    return false;
  }

  return isSame(root.left, subRoot.left) && isSame(root.right, subRoot.right);
}

:::

<br>

**Iterative + Recursive**

:::spoiler 東

/* Time O(m * n) | Space(m + c) ~= Space(m + log(n)) 
   m is the number of root node
   n is the number of subroot node
   c is the depth of subroot node
*/ 
var isSubtree = function(root, subRoot) {
    const queue = [];
    queue.push(root);
    while(queue.length !== 0){
        const currNode = queue.shift();
        if(isSameTree(currNode, subRoot)) return true;
        if(currNode.left) queue.push(currNode.left);
        if(currNode.right) queue.push(currNode.right);
    }
    return false;
};

const isSameTree = function(p, q) {
    if(!p && !q) return true;
    else if(!p || !q) return false;
    else if(p.val === q.val){
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    return false;
};

:::

<br>

:::spoiler Hao (need fix)

function BfsTraverser(root) {
  this.queue = [root];

  this.next = function() {
    const node = this.queue.shift();
    
    node.left && this.enqueue(node.left);
    node.right && this.enqueue(node.right);

    return node;
  }

  this.enqueue = function(node) {
    this.queue[this.queue.length] = node;
  }
}

var isSubtree = function(root, subRoot) {
  const isSubtreeInner = (treeA, treeB) => {
    let shouldLoop = true;
    let res = false;

    while (shouldLoop) {
      const [valA, valB] = [treeA.next()?.val, treeB.next()?.val];

      if (valA === valB && valA === undefined) {
        shouldLoop = false
        res = true;
      } else if (valA !== valB) {
        shouldLoop = false
      }
    };

    return res;
  };

  let res = false;
  const tree = new BfsTraverser(root);

  while (tree.queue.length) {
    const node = tree.next();

    if (node.val === subRoot.val) {
      if (isSubtreeInner(new BfsTraverser(node), new BfsTraverser(subRoot))) res = true;
    }
  }

  return res;
};

:::

---

## Supplement / Discussion
Approach 2: String Matching

- 黑色數字：是 Preorder 經過時紀錄的
- <span class="red">紅</span>色數字：是 Inorder 經過時紀錄的
- <span class="green">綠</span>色數字：是 Postorder 經過時紀錄的

> [複習 pre-order, in-order, post-order](https://hackmd.io/t65f76ofTj-IQjh7xzViWA)

/*
    Time O(M+N) | Space O(M+N) -  where M is the number of nodes in the subRoot, where N is the number of nodes in the tree
*/

var isSubtree = function(root, subRoot) {
  const subRootStr = convertString(subRoot)
  const rootStr = convertString(root)
  return rootStr.includes(subRootStr);
};

function convertString(root, rootStr = ""){
    if (!root) return rootStr;

    rootStr += root.val
    rootStr = convertString(root.left, rootStr)
    rootStr += root.val
    rootStr = convertString(root.right, rootStr)
    rootStr += root.val

    return rootStr
}

## Reference
https://ithelp.ithome.com.tw/articles/10280308

<style>
.red {
color: red;
}

.green {
color: green;
}
</style>