Subtree of Another Tree

Subtree of Another Tree is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Serialization and Deserialization subpattern.

Problem statement

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].

- -104 <= root.val <= 104

- -104 <= subRoot.val <= 104

Topics and companies

Topics: Tree, Depth-First Search, String Matching, Binary Tree, Hash Function.

Reported in interviews at Amazon, Microsoft, Facebook.

How to practise Subtree of Another Tree on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n), m is the number of nodes of s, n is the number of nodes of t time and O(h), h is the height of s space.

Open Subtree of Another Tree in the code editor, or read the Subtree of Another Tree editorial for a worked solution with its approach and complexity analysis.

Where Subtree of Another Tree sits in the DSA pattern sheet

• Tree Traversal Patterns (DFS & BFS) pattern guide
• Serialization and Deserialization subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Subtree of Another Tree

Other problems that use the same Serialization and Deserialization and Tree Traversal Patterns (DFS & BFS) techniques:

• Find Duplicate Subtrees — Medium, same subpattern
• Serialize and Deserialize Binary Tree — Hard, same subpattern
• All Nodes Distance K in Binary Tree — Medium, same pattern
• Balanced Binary Tree — Easy, same pattern
• Binary Search Tree Iterator — Medium, same pattern
• Binary Tree Inorder Traversal — Easy, same pattern