Subtree of Another Tree

Easy · Trees

You are given the roots of two binary trees, a main tree and a candidate tree. Determine whether the candidate tree appears anywhere within the main tree as an exact match, meaning there exists some node in the main tree such that the tree hanging from it has identical structure and identical values to the candidate tree. Return true if such a node exists, otherwise return false.

Examples

Input:  root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true
Why:    The node with value 4 and its children exactly match subRoot in structure and values.

Input:  root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false
Why:    The subtree rooted at 4 has an extra node (0), so it does not match subRoot exactly.

Input:  root = [1,1], subRoot = [1]
Output: true
Why:    The single-node left child with value 1 matches subRoot which is just a lone node valued 1.

Constraints

1 <= number of nodes in root <= 2000, 1 <= number of nodes in subRoot <= 1000, -100 <= node value <= 100

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Subtree of Another Tree

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Subtree of Another Tree. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.