572. Subtree of Another Tree
Subtree of Another Tree (LeetCode 572) 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.
How to solve Subtree of Another Tree
Subtree of Another Tree is a Tree Serialization and Deserialization problem, part of Tree Traversal Patterns (DFS & BFS). Learn to serialize and deserialize binary trees. Convert trees to strings and reconstruct them.
Work towards the solution in these steps:
- Which approach is better here- recursive or iterative?
- If recursive approach is better, can you write recursive function with its parameters?
- Two trees <b>s</b> and <b>t</b> 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?
The reference solution runs in O(m * n) time and O(h) space.
The Subtree of Another Tree solution and editorial walks through the full approach with reference code.
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) time and O(h) 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
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
Subtree of Another Tree FAQ
What is the LeetCode number of Subtree of Another Tree?
Subtree of Another Tree is LeetCode problem 572, rated Easy.
What pattern is used to solve Subtree of Another Tree?
Subtree of Another Tree is a Tree Serialization and Deserialization problem. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Serialization and Deserialization subpattern.
What is the time complexity of Subtree of Another Tree?
The reference solution runs in O(m * n) time and O(h) space.
Which companies ask Subtree of Another Tree?
Subtree of Another Tree has been reported in interviews at Amazon, Microsoft, Facebook.