Check if a binary tree is sub-tree of another binary tree in space O(1)
Given two binary trees t1 and t2, check if tree t2 is sub-tree of tree t1. A sub-tree of tree T1 is a tree T2 having any one of the nodes 'n' and all the descendants of node 'n'.
In the following example, the middle tree - 'Tree_1' is sub-tree of leftmost tree - 'Tree_0'. Note that the rightmost tree - 'Tree_2' is not a sub-tree of 'Tree_0' because of the absence of node 8.
Video coming soon!
Subscribe for more updates
Preparing for interviews? IDeserve team is here to help.
Create your profile
Create your profile, and here is what you will get:
1: Interview practice platform.
2: Once you are ready to take the interview, IDeserve team will help you get connected to the best job opportunities.
3: Personalized mentorship from IDeserve team once your interview process has started.
Creation of profile shouldn't take more than 2 minutes.
If function checkIfSubtree(TreeNode bigTreeRoot, TreeNode smallTreeRoot) implements this algorithm then the steps of this intuitive algorithm are as following - 1. If 'smallTreeRoot is equal to null' then return true since 'null' tree is sub-tree for any tree. 2. If condition #1 is not true then check if 'bigTreeRoot is equal to null'. If it is then return false since null tree cannot have any sub-tree except null tree for which we have already checked in #1. 3. If both conditions #1 and #2 are not true then check if value of smallTreeRoot is equal to value of bigTreeRoot. 4. If condition #3 evaluated to true then we check if left sub-tree of smallTreeRoot exactly matches to left sub-tree of bigTreeRoot and right sub-tree of smallTreeRoot exactly matches to right sub-tree of bigTreeRoot. If both sub-trees match then we return true since we know that smallTree is now a sub-tree of bigTree. 5. If either #3 or #4 evaluate to false then we check if left sub-tree of bigTreeRoot contains smallTree or right sub-tree of bigTreeRoot contains smallTree. For checking this we simply make recursive calls.
Time complexity for this approach is O(n^2) and space complexity for this approach is O(1).
Support us by whitelisting IDeserve in your ad-blocker.