Binary Trees Depth first: return a value up
347. Subtree of Another Tree
You are given root and subRoot, the root nodes of two binary trees. Return true if some subtree of
root is the same tree as subRoot, and false otherwise.
The subtree of a node is the node together with everything below it: its children, their children, and
so on down to the leaves. The whole tree root is also one of its subtrees. Two trees are the same when
they have the same shape, and each node holds the same value as the node in the same place in the other
tree.
The examples write a tree level by level, from left to right, with null where a child is missing. So
root = [5,8,null,3] is the root 5 with a left child 8 and no right child, and 8 has a left child 3. The
missing children after the last node are left out.
Example 1
Input: root = [5, 3, 8, 1, 4, null, 9], subRoot = [3, 1, 4]
trueExplanation: The node 3 in root has the children 1 and 4, and both are leaves. So the subtree of 3 is the same tree
as subRoot.
Example 2
Input: root = [5, 3, 8, 1, 4, null, 9, null, null, 2]
subRoot = [3, 1, 4]
falseExplanation: Now 4 has a left child 2, so the subtree of 3 has four nodes. It is not the same as subRoot, and no
other node holds 3.
Example 3
Input: root = [-2, -2], subRoot = [-2]
trueExplanation: The root −2 has a child, so its subtree has two nodes. Its left child −2 is a leaf, and that one-node
subtree is the same as subRoot.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ number of nodes in root ≤ 1051 ≤ number of nodes in subRoot ≤ 105-109 ≤ Node.val ≤ 109- Each tree has at most 1000 levels.
Clarifying questions
What you would ask an interviewer before writing any code.