CODEWITHSUNDEEP
algorithmtreebinary-tree
amey91
amey91

Reputation: 562

Binary subtree detection - Why to compare 2 traversals

  1. Why do we need to compare in-order traversal string AND pre-order traversal string to determine if a tree is a subtree of a bigger tree? Why is 1 traversal string not enough?
  2. Can we replace one of the above strings with the post-order traversal string?

Assume:

  1. I have an unbalanced binary tree. This is NOT necessarily a binary search tree.
  2. Data at inner nodes and leaves can be compared using a given compareTO() method
  3. The tree is huge, thus making use of suffix trees impossible. Assume normal recursion is possible.

Upvotes: 1

Views: 218

Answers (1)

Mateusz Dymczyk
Mateusz Dymczyk

Reputation: 15141

Ad1. Let's say you have your bigger tree:

     5
   /
  6     <something>
 / \
7   3
   /       
  2

Now notice that the inorder traversal of the subtree rooted at node 6 will be [7,6,2,3]. Now tell me what will be the inorder traversal of the following tree:

  6
 / \
7   2
     \      
      3

You guessed it: [7,6,2,3]. Inorder traversal does not, in general case describe a single binary tree but a number of binary trees. Should this be a binary search tree then you only need 1 preorder or postorder traversal since the inorder traversal will always be the same (all nodes in a sorted order).

Ad2. You can reconstruct a tree with inorder and preorder or postorder traversals. You cannot, in the general case, reconstruct a tree with a preorder and postorder traversals, there might be more than 1 option. The only case where you can do that is for a full binary tree (each node, except the leaves, has to have 2 children).

Upvotes: 2

Related Questions