Problem 🤔

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1

Given tree s:

Given tree t:

Output: true

Example 2

Given tree s:

Given tree t:

Output: false

Real World Applications 🌎

We compare trees more often than you’d think! There are 2 ways to go about this.

Compare all nodes while traversing together - run all possibilities How does this work? Let’s imagine we have a recursive util function called isMatch that takes two nodes and returns whether they are equal trees. We can consider all the different options we have. for matching trees.

1) The trees are exactly identical.

2) t is a subtree of s. In this case, starting from some node in s the trees will be a match.

Now, let’s discuss the implementation of the isMatch helper. We can implement this recursively. Let’s start by looking at the bases cases:

1) 1 subtree is null and the other is not null. This would mean False.

2) Both are null. This would give us True.

3) We are at a node that is equal. Let’s recursively check all the nodes to the left and right.

Naive Solution 💡

Did that feel tedious? I’m hoping it does!

Complexity Analysis 🧮

Time Complexity

Run time: O(|s| * |t|)

Here we denote the number of nodes in s as |s| and t as |t|.

Worst case here we will have to check all the nodes in s as potential root nodes of subtree t.

Space Complexity

O(max(|s|, |t|))

The depth of our recursive stack.

Cool? It’s alright for a start. Do we really need to check the entirety of t (|t|) so many times?

The Finer Details 🔎

No, we don’t!

Optimal Solution - Merkle Trees 💡

We’re going to leverage a very clever data structure called a merkle tree. In short, for every node in the tree we can create a merkle hash for its subtree.

This is actually used a lot in the real world! Great examples are:

1) Git - What tree are we referring to here? Imagine main as the root node of the tree. Every time a developer makes a branch (mind blown?) the tree gets larger. When we pull from main or try to push to main, git will create merkle nodes for every snapshot and then compare to know if they are different!

2) Blockchain, this allows nodes to easily validate payment history without having to sync a full node.

Complexity Analysis 🧮

Time Complexity

Run time: O(|s| + |t|)

We traverse each tree once initially to create the merkle hashes for every node.

Space Complexity

O(max(|s|, |t|))

Depth of the recursive stack.

Takeaways 🎉🥳

• A great takeaway from this problem is that we can modify binary search for our needs! We just need to adjust the search termination condition.
• This is only 1 example of such a modification. Can you think of more?

Resources 📚

Leetcode

• Cracking the Coding Interview, 4.10 Check Subtree