The Blind 75 Leetcode Series: Subtree of Another Tree

Photo by Chris Ried on Unsplash

572. Subtree of Another Tree

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

Given 2 trees, we want to check if one of them is a subtree of the other. A tree is only a subtree of another if all children are the same. This means we cannot have some additional node as child attached to the part of tree we want to check.

We want to check for a few things:

1. do we expect empty tree and/or subtree?
2. what kind of values do we expect in the nodes?

Let’s see the interviewer tells us that we don’t have to worry about empty trees (as it is in this leetcode problem) and all nodes contain only integers. We can then continue.

In order for tree A to be a subtree of tree B, A’s root must be somewhere in B. This is our first condition to…