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

Example:

Approach:

We know that identifying 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 traversal of treeA and store it in a String say inorderA.
• Do the inorder traversal of treeB and store it in a String say inorderB.
• Do the postorder traversal of treeA and store it in a String say postorderA.
• Do the postorder traversal 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)

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

Related Problems:

- Lowest Common Ancestor in a Binary Tree (Not Binary Search Tree). Hard
- Construct a binary tree from given Inorder and Level Order Traversal Hard
- Get the Height of a Node in a Binary Tree Medium
- Find and Print Full Nodes in a Binary Tree Beginner
- Find the Height of a tree without using Recursion Medium