Leetcode Accepted

PriyankaKhire · PriyankaKhire · commit 093a533e9a79 · 2021-08-22T20:54:59.000-07:00
diff --git a/Blind 75/Programs/Subtree of Another Tree.py b/Blind 75/Programs/Subtree of Another Tree.py
@@ -0,0 +1,53 @@
+# Subtree of Another Tree
+# https://leetcode.com/problems/subtree-of-another-tree/
+
+# Definition for a binary tree node.
+# class TreeNode(object):
+#     def __init__(self, val=0, left=None, right=None):
+#         self.val = val
+#         self.left = left
+#         self.right = right
+class Solution(object):
+    def sameTrees(self, t1, t2):
+        # if we reach null node of both trees then return true
+        if (not t1 and not t2):
+            return True
+        # if one tree has nodes, but another doesn't we return false
+        if ((not t1) and t2):
+            return False
+        if (t1 and (not t2)):
+            return False
+        # if left sub tree is not the same we return False and early terminate.
+        if not(self.sameTrees(t1.left, t2.left)):
+            return False
+        # if values are not same we reutrn false and early terminate without checking further.
+        if (t1.val != t2.val):
+            return False
+        # if right sub tree is not the same we return false and early terminate
+        if not(self.sameTrees(t1.right, t2.right)):
+            return False
+        # else we return true to keep looking further.
+        return True
+    
+    def findSubTree(self, root, subRoot):
+        # if it's a null node, we return back.
+        if not root:
+            return 
+        # if we find current node value = subTree root value we check if they are same or not
+        if (root.val == subRoot.val):
+            if (self.sameTrees(root, subRoot)):
+                return True
+        # if sub tree found in left sub tree we return true and early terminate.
+        if (self.findSubTree(root.left, subRoot)):
+            return True
+        # if sub tree found in right sub tree we return true and early teminate
+        if (self.findSubTree(root.right, subRoot)):
+            return True
+        
+    def isSubtree(self, root, subRoot):
+        return self.findSubTree(root, subRoot)
+        """
+        :type root: TreeNode
+        :type subRoot: TreeNode
+        :rtype: bool
+        """
diff --git a/Blind 75/README.md b/Blind 75/README.md
@@ -255,7 +255,11 @@
           <li><a href="Programs/Serialize and Deserialize Binary Tree - LevelOrder Toomuch Space.py">Too much space with level order</a>: This exceeded leetcode space limit. </li>
         </ul>
       </li>
-      <li>Subtree of Another Tree</li>
+      <li><a href="Programs/Subtree of Another Tree.py">Subtree of Another Tree</a>
+        <p><b>Approach</b>: Recursive function similar to inorder traversal that checks if 2 sub trees are same or not.
+          Another function that checks if the current node in the larger tree is same as the root of sub tree, then it calls the previous function to check if the subtrees are same or not.
+        </p>
+      </li>
       <li>Construct Binary Tree from Preorder and Inorder Traversal</li>
       <li>Validate Binary Search Tree</li>
       <li>Kth Smallest Element in a BST</li>
