In this post, I note the approach and my thought process about determining whether a given smaller tree (t2) is a subtree of another larger tree (t1). First, the approach: Since I know t2 is smaller and it is to be matched/found in a larger tree t1, I'll take the approach of scanning through the larger tree t1, and t1's children, by trying to find a match of t2 in t1's left child tree and find a match of t2 in t1's right child tree, recursively. Thought Process1. Define the contract of the function for finding subtree boolean subTree(TreeNode t1, TreeNode t2) 2. Consider boundary conditions for finding subtree Consider what if the small tree t2 is null, and what if the bigger tree t1 is null. 3. Put in core logic as mentioned in the above 'approach' section for finding a match so I can say a subtree is found. If t1.data is the same as t2.data, further check if they are the exactly match. However, if t1.data is not the same as t2.data, check if t2 is a subtree of t1.left or a subtree of t2.left. 4. Implement the logic for checking if 2 trees are exactly the same. Code Sampleboolean subTree(TreeNode t1, TreeNode t2) {
0 Comments
Leave a Reply. 
Categories
All
Archives
December 2017
