I want to find out whether binary tree T2 is a subtree of of binary tree T1. I read that one could build string representations for T2 and T1 using pre-order and in-order traversals, and if T2 strings are substrings of T1 strings, T2 is a subtree of T1.
I am a bit confused by this method and not sure about its correctness.
From wiki: "A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T."
In the following example:
If we build the strings for T2 and T1:
preorder T2: "1,2,3"
preorder T1: "1,2,3,4"
inorder T2: "2,1,3"
inorder T1: "2,1,3,4"
The T2 strings are substrings of T1, so using the substring matching method described above, we should conclude T2 is a subtree of T1.
However, T2 by definition shouldn't be a subtree of T1 since it doesn't have all the descendants of T1's root node.
There is a related discussion here, which seems to conclude the method is correct.
Am I missing something here?