Thursday, April 21, 2016

A binary tree is substree of another binary tree

April 21, 2016


It is the great experience to review the recursive function through the algorithm called "Is subtree". Depth first search algorithm is very basic one using recursive function call, it is the fast and quick way to write an algorithm and also very popular in the interviews.

Problem statement:

Time Complexity: Time worst case complexity of above solution is O(mn) where m and n are number of nodes in given two trees.

Another solution:

O(n) time, special case handling - for leaf node of tree - append null 

Question and answers:

1. What do you learn through this study? How long does it take you to figure out things? 

Answer: First, it is about the subtree definition: it should be uniquely defined; for any node in the tree, the subtree starting from the node is only one. In other words, the node is the start, and all leaf nodes underneath should all be included.

2. The very good way to think recursively; do not repeat the work, do not do the extra work; only work on root node, since every node can be root node; get in the loop or recursive function. 

3. Let us walk through the code and add some comment: The code link is here

Dec. 25, 2016

Read the code review on

Algorithm called "is subtree"

Follow up 

June 17, 2017

Find out leetcode algorithm related algorithm. 

Blog to read:
Need to review KMP algorithm - strstr - O(N) algorithm:

No comments:

Post a Comment