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)

Run This Code

Code:

Tree A : 3 2 1 5 4 6
Tree B : 5 4 6
true

Also Read:

- Find all subsets of size K from a given number N (1 to N) Medium
- Swap Nodes in pairs in a Linked List by changing links Medium
- Depth First Search/Traversal in Binary Tree Beginner
- Find the Distance between Two Nodes of a Binary Tree. Hard
- Construct a Binary Tree from Given Inorder and Depth-First-Search. Hard
- Backtracking - N Queens Problem - Better Solution Hard
- Print all subarrays using recursion Medium
- Merge Sort - Updated - Most Efficient ways to Implement Medium