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.