Check if a binary tree is sub-tree of another binary tree in time O(n)
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.
The algorithm is based on a simple idea that any binary tree could be uniquely represented by using in-order and pre-order traversal.
To check if tree 'smallTree' is sub-tree of tree 'bigTree', the steps of the algorithm are as following - 1. Find inorder traversals of 'smallTree' and 'bigTree'. Store them is string inorderForSmallTree and inorderForBigTree respectively. 2. Find preorder traversals of 'smallTree' and 'bigTree'. Store them is string preorderForSmallTree and preorderForBigTree respectively. 3. For 'smallTree' to be a sub-tree 'bigTree', string 'inorderForSmallTree' should be a substring of string 'inorderForBigTree' and string 'preorderForSmallTree' should be a substring of string 'preorderForBigTree'.
We could have also used post-order traversal string instead of pre-order traversal string in this algorithm. Please checkout function checkIfSubtree(TreeNode bigTree, TreeNode smallTree) in code snippet for implementation details.
The time complexity of this algorithm is O(n) since traversal string could be formed in O(n) time and using KMP algorithm substring check could also be done in O(n) time; though for simplicty in the implementation we have used in-built java string API for substring check.
Space complexity for this approach is O(n) for storing traversal strings.
Support us by whitelisting IDeserve in your ad-blocker.