lowest common ancestor

I like to write down my practice today.

235. Lowest Common Ancestor of a Binary Tree binary search in BST
236. Lowest Common Ancestor of a Binary Tree time out using string, need help
236. Lowest Common Ancestor of a Binary Tree time out using list, need help
236. Lowest Common Ancestor of a Binary Tree optimal solution bottom up with reasoning

Follow up 

May 10, 2019


I learned one more solution, and here is the post. 

I solved my first two practice with time out problem applying the idea to find root to p or q path. Here is the solution. 

I like to make a list of things I have practiced on this algorithm:


Recursive
1. Using recursive, learn how to define recursive function, simple and clear.

BFS
I also study the code and write a C# solution using BFS to store all nodes with their parent node. 

Backtracking 
I learn to solve timeout issue in my naive solution in the first practice 2019. 

Also backtrack space complexity is much less compared to my naive approach. 

Post order traversal - bottom up 
How to define a simple and easy recursive function? I learn one solution and like it. 

The solution folder is here. 

Topics 

1. BFS
2. child-parent map
3. Fix naive solution timeout with complicated function
4. how to build a path from p or q to root
5. how to build a path from root to p
6. Naive solution with Timeout and Complicated function
7. Post order traversal
8. recursive function - Do not understand
9. Recursive solution Easy to understand
10. Recursive solution with backtracking
11. Timeout challenge

Here is the folder to look up problems and solution based on topics I worked on. 

Follow up 

May 29, 2019
I continue to learn the algorithm as an interviewer on interviewing.io, I give out the algorithm to interview others more than three times, one time the interviewee is Amazon SDE II in Seattle, he showed me how to design a recursive function to return if one node is found in recursive function, in early May; And later, on May 28, 2019, one engineer showed me how to solve it using recursive function assuming that given node p and q in binary tree, and he is an engineer in Motorola. 

Topics

child-parent map, parent node, BFS (May 11, 2019)
Post order traversal (May 27, 2019)

how to build a path from p or q to root (May 11, 2019)
how to build a path from root to p (May 23, 2019)

recursive function - Confused and more work later (May 8, 2019)
Recursive solution Easy to understand (May 15, 2019)
Recursive solution with backtracking (May 23, 2019)
C# recursive function to find lowest common ancestor given p and q are in the binary tree (May 28, 2019)
C# recursive function to find lowest common ancestor given p and q (May 28, 2019)

Naive solution with Timeout and Complicated function
Timeout challenge (May 7, 2019)
Timeout challenge - using a string to store path (May 7, 2019)
Fix naive solution timeout with complicated function (May 13, 2019)
learn elegent solution using back tracking and space efficiency, avoid timeout (May 23, 2019)


June 25, 2019
Three practice for three ideas; I like to be a master of the lowest common ancestor!
find one path first and then look up path for second given node q
C# find path from given node p to root first and then find q and lowest common ancestor
find one path first top down and then look up path for second given node q
C# Find top down path for a given node p and then find q's path and look up lowest common ancestor
backtrack to find path from root node to given node p
C# backtrack to find root node to given node p