algorithms-python/algorithms/tree/is_subtree.py at master · ivan1911/algorithms-python · GitHub

History

71 lines (56 loc) · 1.11 KB

Raw

"""

Given two binary trees s and t, check if t is a subtree of s.

A subtree of a tree t is a tree consisting of a node in t and

all of its descendants in t.

Example 1:

Given s:

/ \

4 5

/ \

1 2

Given t:

/ \

1 2

Return true, because t is a subtree of s.

Example 2:

Given s:

/ \

4 5

/ \

1 2

Given t:

/ \

1 2

Return false, because even though t is part of s,

it does not contain all descendants of t.

Follow up:

What if one tree is significantly lager than the other?

"""

import collections

def is_subtree(big, small):

flag = False

queue = collections.deque()

queue.append(big)

while queue:

node = queue.popleft()

if node.val == small.val:

flag = comp(node, small)

break

else:

queue.append(node.left)

queue.append(node.right)

return flag

def comp(p, q):

if p is None and q is None:

return True

if p is not None and q is not None:

return p.val == q.val and comp(p.left,q.left) and comp(p.right, q.right)

return False

algorithms-python/algorithms/tree/is_subtree.py at master · ivan1911/algorithms-python · GitHub

Expand file tree

Breadcrumbs

is_subtree.py

Latest commit

History

Breadcrumbs

is_subtree.py

File metadata and controls