A Copy Inside the Tree

Easy

You are given the roots of two binary trees: a large one, root, and a sample, pattern. The subtree of a node is that node together with all of its descendants; the whole tree also counts as the subtree of its root. Return true if some node of root has a subtree identical to pattern, matching both in shape and in node values. Otherwise return false.

Example 1

root=tree_node([7, 2, 9, 1, 3]), pattern=tree_node([2, 1, 3]) → True

Node 2 together with all of its descendants is exactly pattern.

Example 2

root=tree_node([7, 2, 9, 1, 3, None, None, 5]), pattern=tree_node([2, 1, 3]) → False

Node 1 has an extra child 5, so the subtree under node 2 is larger than pattern, and no exact copy exists.

Example 3

root=tree_node([4, 4]), pattern=tree_node([4]) → True

The leaf 4 with its (empty) descendants matches pattern.

Constraints

root has between 1 and 2000 nodes
pattern has between 1 and 1000 nodes
−10⁴ ≤ node value ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Binary Tree String Matching Hash Function

Similar problems

Left, Node, Right Easy Identical Trees Easy Mirror-Image Tree Easy Tree Height Easy Evenly Grown Tree Easy

Input

root=tree_node([7, 2, 9, 1, 3]), pattern=tree_node([2, 1, 3])

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 130 tests on the server, hidden ones included.