Is Subtree of Another Tree easy or hard?

Subtree of Another Tree is classified as an Easy problem on LeetCode with about a 50% acceptance rate. The logic is straightforward once you understand how to compare two binary trees recursively.

Subtree of Another Tree Python/Java solution

In Python or Java, the typical solution defines a helper function that checks whether two trees are identical using recursion. The main function traverses the root tree and calls this helper whenever node values match the root of subRoot.

How to solve Subtree of Another Tree in O(n)?

Serialize both trees using preorder traversal while inserting markers for null nodes. Then check if the serialized string of subRoot appears inside the serialized string of root. Using a linear string matching algorithm like KMP makes the overall complexity O(n + m).

What is the best approach for Subtree of Another Tree?

The most common approach uses recursive DFS. Traverse every node of the main tree and run a second DFS to check if the subtree rooted at that node is identical to subRoot. This method is simple to implement and works well in interviews, though the worst-case time complexity is O(n * m).

Is Subtree of Another Tree asked at Google/Amazon/Meta?

Subtree comparison problems frequently appear in interviews at major tech companies such as Amazon, Google, and Meta. They test understanding of binary tree traversal, recursion, and structural equality checks, which are core tree interview concepts.

What data structure is used in Subtree of Another Tree?

The problem primarily uses a binary tree data structure. Solutions rely on depth-first search recursion to traverse nodes, and some optimized methods additionally use strings or hash-based matching after serializing the tree structure.

What is the time complexity of Subtree of Another Tree?

The DFS comparison approach runs in O(n * m) time where n is the number of nodes in the main tree and m is the number of nodes in the subtree. An optimized solution using preorder serialization and efficient substring search such as KMP can reduce the time complexity to O(n + m).

Description Hints 4 Solution Video 14:15

572. Subtree of Another Tree

Easy52.0% acceptance8 companies

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.

Example 1:

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

Example 2:

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

Constraints:

The number of nodes in the root tree is in the range [1, 2000].
The number of nodes in the subRoot tree is in the range [1, 1000].
-10⁴ <= root.val <= 10⁴
-10⁴ <= subRoot.val <= 10⁴

Asked at 8 companies

eBay Compass Jump Trading Meta Bloomberg

Google Amazon Microsoft

Topics

Hints open one at a time

Hint 1

Which approach is better here- recursive or iterative?

Hint 2

If recursive approach is better, can you write recursive function with its parameters?

Hint 3

Two trees s and t are said to be identical if their root values are same and their left and right subtrees are identical. Can you write this in form of recursive formulae?

Hint 4

Recursive formulae can be: isIdentical(s,t)= s.val==t.val AND isIdentical(s.left,t.left) AND isIdentical(s.right,t.right)

14:15

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution