Determine if a binary tree is subtree of another b

Question

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:

T2:
  1
 / \
2   3

T1:
  1
 / \
2   3
     \
      4

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?

Answer 1

The definition of sub-tree of a tree should be same as the definition of sub-string of a string. Think of it like this: 1. sub-string has begins-with, contains and ends-with. 2. Tree should also have the same definition but generalized to suit the Tree data structure. 3. The generalization is from 1 dimensional for string to 2 dimensional for tree.

Answer 2

I'm reading the same book and doubted its solution as well. I came up with another counter-example that doesn't fall into the potential interpretation that user icepack mentions (of a subtree not necessarily needing all the descendents).

Consider the following trees

T2:
  B
 / \
A   C

T1:
    C
   / \
  B   C
 /
A

preorder T2: 'BAC'
preorder T1: 'CBAC'
inorder T2: 'ABC'
inorder T1: 'ABCC'

Again, the T2 strings are substrings of their T1 counterparts and yet T2 is in no way a subtree of T1. Perhaps in the author had ruled out duplicates and specifically mentioned his definition of subtree it could be right, but leaving out that information leaves us with no choice but to consider it an incorrect solution.

Answer 3

Na...This approach is not correct.Because, different trees can have same traversal . For instance here in the given example, the tree is

         26
        /   \
      10     3
    /    \     \
  4      6      3
   \
    30

and the candidate subtrees are

10
/ \
4 6
\
30

and

30
/ \
4 10
\
6

have the same inorder traversal as 4,30,10,6 but the second one isn't subtree

Answer 4

Very interesting question. You seem to be correct. I suppose the issue that you mention arises due to different definitions of subtree in math (graph theory) and computer science. In graph theory T2 is a proper subtree of T1.

Answer 5

Assuming you got this from the book "Cracking the Coding Interview", the author also mentions that to distinguish between nodes with the same values, one should also print out the null values.

This would also solve your problem with the definition of a subtree (which is correct as also described in the book)

preorder T2: "1, 2, null, null, 3, null, null" preorder T1: "1, 2, null, null, 3, null, 4, null, null" inorder T2: "null, 2, null, 1, null, 3, null" inorder T1: "null, 2, null, 1, null, 3, null, 4, null"

As you can see, T2 is not a subtree of T1