Subtree of Another Tree
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Does the big tree contain the small tree as a subtree (same shape and values, taken from some node down to all its descendants)?
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1You already know how to check if two trees are identical.
- Hint 2Try that check starting from every node of the big tree.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
You want to know whether a small photograph of a family branch appears somewhere inside a huge family tree. You walk through the big tree person by person; at each person you hold the small photo against the branch that starts there and check if the two match exactly. One exact match anywhere is enough.
- The obvious way
This is the natural approach already: the cost is O(n x m) in the worst case.
- The key insight
The small tree is a subtree if it equals the tree at the current node, OR it is a subtree of the left child, OR of the right child. Reuse the same-tree check for the first part. An empty big tree contains nothing (unless the small one is also empty).
- The algorithm
- Big tree empty? Not found (False).
- Is the tree starting here the same as the small tree? Then True.
- Otherwise look in the left child's tree, then in the right child's tree.
Watch it run
Examplebig = [3, 4, 5, 1, 2], small = [4, 1, 2]
At the root 3: the tree starting here is not the same as [4, 1, 2]. Move on.
no match at 3
Where people slip
- A subtree must include ALL descendants: [4, 1] is not a subtree of a node 4 that also has a right child.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def is_subtree(root, sub_root):
def same(a, b):
if a is None and b is None:
return True
if a is None or b is None or a.val != b.val:
return False
return same(a.left, b.left) and same(a.right, b.right)
if root is None:
return sub_root is None
return same(root, sub_root) or is_subtree(root.left, sub_root) or is_subtree(root.right, sub_root)Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.