Leetcode 236: Binary Tree Lowest Common Ancestor - warm up practice (IV)

May 23, 2016

 First thing in Canadian Victoria long weekend morning, 9:00am, warm up an algorithm. Write the code using inorder preorder traversal, using recursive function, find binary tree lowest common ancestor.

 Latest practice on this problem (Less than 24 hours ago):
http://juliachencoding.blogspot.ca/2016/05/leetcode-236-lowest-common-ancestor_22.html

C# practice on May 23, 2016
https://gist.github.com/jianminchen/c9941b8daf6afe51d049ecb5f5a17e19

Questions and answers:

1. How is your warm up practice?

Answer: Julia likes to train herself, discipline herself to write bug free code, ready to production code if she knows the idea to solve the problem, and also has strong analysis of problem solving already through multiple practice, over 5+ hour practice.

May 22, 2016 practice is based on geeksforgeeks.com blog, and then, May 23, 2016 practice is based on her own analysis and reasoning, the code has more than 2 differences. Good ones.

First one, on line 43, return early if p==null or q==null.
line 43: if (root == null || p == null || q == null)

Second one: line 56
line 56: if (findPath(root.left, search, path) || findPath(root.right, search, path))
                return true;

old version:
line 67: if ( (root.left  != null && findPath(root.left, path, searchNode)) ||
                 (root.right != null && findPath(root.right, path, searchNode)) )
                return true;

old version line 67, the condition checking is a giant expression, root.left != null is not neccessary, let it fall through to allow findPath to do the checking, code is much more clean.

2. You already practiced preorder and post order traversal to solve binary tree least common ancestor problem. How about inorder traversal?

Answer: Inorder traversal does not work out this algorithm. Since we are looking for paths from root to search nodes, in the inorder traversal the root node's position is unknown. It is neither the first one as preorder traversal does, nor the last one as post order traversal does. It is somewhere in the middle.

Leetcode 236: Lowest Common Ancestor - Warm up practice

May 21, 2016

  Julia took more than 10 hours to play with the tree traversal algorithm. Then, she likes to write down the algorithm bug free within 20 - 30 minutes. It is a warm up practice. Just enjoy the adventure and see how many issues are not resolved.

 Here is the second blog she worked on more than 10 hours on May 22, 2016:
http://juliachencoding.blogspot.ca/2016/05/leetcode-236-lowest-common-ancestor.html

Previous blogs: (April 22, 2016)
http://juliachencoding.blogspot.ca/2016/04/find-lowest-common-ancestor-of-two.html

http://juliachencoding.blogspot.ca/2015/07/leetcode-lowest-common-ancestor-in.html

Review solutions again:
https://github.com/jianminchen/LowestCommonAncestorInBinaryTree/blob/master/LowestCommonAncestorB.cs

Now, start her warm up practice:
 May 21, 2016 9:18pm - 9:48pm - 30 minutes taken

https://gist.github.com/jianminchen/5aa398b8c6e9f13c5a11213ef03cb5bc

Julia found out a few things:

1. First, a  new variable is added: stopTraversal on line 49.
   When both two nodes p and q are found, stop to traversal the binary tree.

   Julia also learned how to break two while loop:
C# does not allow  two "break; ", complaining that the second "break; " unreachable.

   4 lines are added:
   line 49, line 69, line 76, line 77.

   set StopTraversal = true, and then,  break the inside while loop, next to the while loop, check
   if(StopTraversal == true) then, break outside loop.

   The code Julia studied and practiced before just break inside while loop only. So, here is the change.
   line 74 in the following version needs some extra work:
   https://gist.github.com/jianminchen/388114d99020972413464a072e5e9a9b

2. Julia forget to declare the stack at the beginning, and also, declare two lists for p and q.

Question and answer:

1. Why do the warm up practice right away? 

Answer:
Julia knows the importance to learn an algorithm a time. Keep working on the code, until it works perfectly, until she makes all mistakes and learns lessons. Afterwards, she may start to learn to analyze the algorithm, even memorize the algorithm easily.

The code is executable, optimized, every line is executed and she pays some attention on them how to optimize.

Practice makes perfect. Show progress, that is mental toughness, that is value of sharing - document progression to excellence.

2. Write C# version based on the blog:
http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/