CS Interview Question: Subtree of a tree

janac
3 min readMay 26, 2020

Problem Statement

From: https://leetcode.com/problems/subtree-of-another-tree/solution/

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:

     3
/ \
4 5
/ \
1 2

Given tree t:

   4 
/ \
1 2

Return true, because t has the same structure and node values with a subtree of s.

Example 2:
Given tree s:

     3
/ \
4 5
/ \
1 2
/
0

Given tree t:

   4
/ \
1 2

Return false.

Proof

This solution is 96% of other solutions submitted on Leetcode.com.

Solution

The Code

How to think of this problem

  • When you see that the problem is related to trees, you must immediately ask yourself — can I use a DFS tree traversal algorithm? Namely: preorder, in-order, and postorder traversal.
  • Since we need to check if a tree is a subtree, we are always checking the root of the subtree first. This is exactly what preorder traversals do, they process the root first, and then continuing traversing down the left/right subtrees.
  • Once we’ve decided to use preorder, we have to consider the edges cases. What if the parent is null, or the subtree is null? We add if statements to handle these cases.
  • Now we create two functions: isSubtree() our main function, and isSame() a helper.

equals()

  • Returns true if two nodes have the same value, and the same children.

--

--

janac

Most of my writing is about software. I enjoy summarizing and analyzing books and self-help videos. I am senior software consultant at LazerTechnologies.com.