Be the first user to complete this post
|
Add to List |
Given two binary trees, check if one binary tree is a subtree of another
Objective: Given two binary trees, check if one binary tree is a subtree of another
Input: Two binary trees
Output: True or false based on whether one tree is subtree of another
Example:

Approach:
We know that to indentity any binary tree can be represented as the combination of either inorder and preorder traversal OR inorder and postorder traversal OR inorder and Level order traversal.
- Say our trees are A and B.
- Do the inorder traveral of treeA and store it in a String say inorderA.
- Do the inorder traveral of treeB and store it in a String say inorderB.
- Do the postorder traveral of treeA and store it in a String say postorderA.
- Do the postorder traveral of treeB and store it in a String say postorderB.
- Check if inorderA contains inorderB AND postorderA contains postorderB then it means treeB is a subtree of treeA.
Time Complexity : O(n)

Code:
Tree A : 3 2 1 5 4 6
Tree B : 5 4 6
true
Also Read: