AM; YourMove: Check if a Tree is a Subtree or not!

link to the actual video

This is the very first blog post of the video description of the of the youtube video released on 3rd April 2017.

The topic for the video is checking if a binary tree is a subtree or not. This video is released as part of video series on trees data structure. The video starts off with describing the problem statement. The definition of a subtree can be sometimes misunderstood therefore the presenter takes the help of Wikipedia to find out the actual definition of a subtree. According to Wikipedia,

    A subtree of a tree T is a tree consisting of a node in T and all of its descendants in 

Afterwards, The presenter right away starts with finding the possible solution for the problem. To solve the problem, The presenter coins concepts like tree traversals. Tree traversals are the algorithms which traverse the tree is some fashion to get the values of the node data. There are 3 very popular tree traversals.

  1. Pre-order
  2. Post-order
  3. In-order

The presenter goes on to explain these traversals.

Pre-Order :

  1. Check if the current node is empty/null.
  2. Display the data part of the root (or current node).
  3. Traverse the left subtree by recursively calling the pre-order function.
  4. Traverse the right subtree by recursively calling the pre-order function.

In-Order :

  1. Check if the current node is empty/null.
  2. Traverse the left subtree by recursively calling the in-order function.
  3. Display the data part of the root (or current node).
  4. Traverse the right subtree by recursively calling the in-order function.

Post-Order :

  1. Check if the current node is empty/null.
  2. Traverse the left subtree by recursively calling the post-order function.
  3. Traverse the right subtree by recursively calling the post-order function.
  4. Display the data part of the root (or current node).

 

After that, Presenter reveals that traversals define few interesting characteristics of a binary tree.

For example.,

  1. If the binary tree is BST then inorder traversal gives us ascending order of the values of the nodes.
  2. For any binary tree, pre/post and inorder uniquely identifies a tree.

2nd point is interesting and can be directly applied to solve our problem i.e to find whether a tree is a subtree of another tree or not. But how? The presenter explains that if a smaller tree’s pre and inorder elements are subarray of bigger tree’s pre and inorder elements respectively then we can confirm that tree is a subtree. The presenter starts implementing the actual algorithm.

 

// method to find if a tree is a subtree

bool BinaryTree::isSubtree(node *big, node *small) {

// data structures to collect the values of the nodes encounterd while traversing the tree

vector<int> preOrderBigCollector;
vector<int> inOrderBigCollector;
vector<int> preOrderSmallCollector;
vector<int> inOrderSmallCollector;

preOrderTraversal(big, preOrderBigCollector);
preOrderTraversal(small, preOrderSmallCollector);

inOrderTraversal(big, inOrderBigCollector);
inOrderTraversal(small, inOrderSmallCollector);

return isSubArray(preOrderBigCollector, preOrderSmallCollector) && isSubArray(inOrderBigCollector, inOrderSmallCollector);

}

 

This is one the efficient solution for this problem. The worst case time complexity for this problem is O(n). But in the video presenter has used a vague approach to find is subarray. Due to that the complexity worsens to O(n2). Therefore, If we use KMP pattern matching algorithm for the same then the ideal time complexity can be achieved.

author’s note:

This is my first post. As you have realized I have I used 3rd person style of writing. I can sometimes criticize myself from what I have done in the video ( of course, for the positive personal growth ). Hope you liked this post!

LIKE + SHARE + SUBSCRIBE to AM;YourMove

https://www.youtube.com/channel/UCkAou6vl72JU7DMFYs84YYg

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s