SWE Prep

Share this post

Check Subtree

sweprep.substack.com

Check Subtree

Sameer Khoja
Sep 4, 2020
1
Share this post

Check Subtree

sweprep.substack.com

Question 8: T1 and T2 are two very large binary trees, with T1 much bigger than T2. Create an algorithm to determine if T2 is a subtree of T1.

One way we can solve this is to search through the larger tree, and see if we find the root node of the smaller tree. If we do find the root node, we can call a method to check whether the subtree of T1 matches T2.

Below is an algorithm that implements the solution:

We’re done!

Similar Questions:

  • Random Node

  • Paths With Sum

  • Unique BSTs

Share this post

Check Subtree

sweprep.substack.com
TopNew

No posts

Ready for more?

© 2023 Sameer Khoja
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing