Introduction
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:
http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-of-another-binary-tree/
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:
http://www.geeksforgeeks.org/check-binary-tree-subtree-another-binary-tree-set-2/
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 stackexchange.com.
Algorithm called "is subtree"
http://codereview.stackexchange.com/questions/6774/check-if-a-binary-tree-is-a-subtree-of-another-tree
http://codereview.stackexchange.com/questions/117325/find-if-a-given-tree-is-subtree-of-another-huge-tree
Follow up
June 17, 2017
Find out leetcode algorithm related algorithm.
Blog to read:
Need to review KMP algorithm - strstr - O(N) algorithm:
http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
No comments:
Post a Comment