LeetCode 572. Subtree of Another Tree

A simple solution beating 99.5% Python3 submission in terms of speed.

Original problem: https://leetcode.com/problems/subtree-of-another-tree/description/


We don’t need to check each of the node of the target Root tree whether it’s matching the subRoot tree. What if we only check those nodes having the same height as the subRoot tree?


Note that M is the number of nodes in the Root tree; and
N is the number of nodes in the subRoot tree.

  1. Compute the height of the subRoot tree by traversing it. (time complexity N)
  2. Compute the height of the Root tree (time complexity M). While traversing it, for those nodes which match the height of the subRoot tree, check if it match the subRoot tree (time complexity logM * N where logM means the number in the worst case i.e. a full/balanced binary tree).


  • Time complexity: O(N + M + NlogM)
  • Space complexity: O(1)


def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def height(node):
if not node:
return 0
return 1 + max(height(node.left), height(node.right))
height_subroot = height(subRoot)

def verify_same_tree(node1, node2):
if not node1 and not node2:
return True
if (not node1 and node2) or (node1 and not node2) or (node1.val != node2.val):
return False
return verify_same_tree(node1.left, node2.left) and verify_same_tree(node1.right, node2.right)

found = False
def height_main(node):
if not node:
return 0
cur_height = 1 + max(height_main(node.left), height_main(node.right))
if cur_height == height_subroot:
if verify_same_tree(node, subRoot):
nonlocal found
found = True
return cur_height

return found




Computer Vision Applied Scientist @ Amazon. https://coldmanck.github.io

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store