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

Leetcode 236: Lowest Common Ancestor - practice (III)

May 22, 2016

  Leetcode 236: Lowest common ancestor 

  Based on the blog:

    http://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/

Julia practices using C#:

user recursive function, use preorder traversal to do search: 

https://gist.github.com/jianminchen/3a9931ecb7818498cbbb47152ed66d89

Reference:

1. Use post order traversal to find the lowest common ancestor in binary tree:
http://juliachencoding.blogspot.ca/2016/05/leetcode-236-lowest-common-ancestor_21.html

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/

Leetcode 236: Lowest common ancestor

May 18, 2016

  Lowest common ancestor:

  http://juliachencoding.blogspot.ca/2016/04/leetcode-236-lowest-common-ancestor-in.html

  Julia's C# practice on May 21, 2016
1. User Stack class ToArray API, keep stack iterator order
code has a bug - index out of range - line 93
https://gist.github.com/jianminchen/2bec8a70ef520e715240a226c01c7371

https://msdn.microsoft.com/en-us/library/415129w1(v=vs.110).aspx

2. Second warm up, just use List.AddRange(Stack), still keep stack iterator order
code has a bug - index out of range - line 93
https://gist.github.com/jianminchen/754f45023f60992211cb34bef6d6254f

3. Third warm up, use the test case in the diagram 1, 2, 3, 4, 5, 6, 7, 8, 9, and then, find out the bug! Big surprise! Every line of code should be optimized, and then examined.

Fix the bug - index out of range - line 93
https://gist.github.com/jianminchen/99585d73e4196136fd87274174dec3b9

4. Fourth warmp up practice, change code while loop code, make it explicitly - loop variable
https://gist.github.com/jianminchen/388114d99020972413464a072e5e9a9b


Make the code more readable about line 93.


 Review blog about post order traversal,

http://juliachencoding.blogspot.ca/2015/09/morris-order-post-order-traversal.html

And then, we can easily find out that the order of output can be implemented using stack, and then, the stack - the root node is always the last one. We can find two nodes p, q through post order traversal, once any one of those two nodes is visited, the path from root to p or q can be retrieved from the stack. Use stack API, move stack content to a list.

So clever, let us recall those images used in the above blog:

The node may be visited more than once, it is better to check if it is one of two input nodes  when first time to visit. 

Also, the stack is kind of tricky, you can peek, if the node is ready to add into post order traversal output, then pop it. 

Questions and Answers:

1. Please write down what you learn through this practice, warmup? How long do you take? 

It takes over 6 hours to get back in tree traversal algorithm. 

The most important to remember that the tree's post order traversal only has 3 parts:

1. Push root node and its left child to the stack, repeat to the end of leftmost node. 

    

2. And then, peek the node has right child or not. In the above diagram, N1 has no right child. 

    if there is one, denoted as N3, then, treat the node N3 as step 1  - push node and its left's child to the end of leftmost node. 

    else, it is ready to pop the node, and add it to traversal result. 

2.  Save a variable as a previous visited node, check the current node relationship to previous node, 

    in the above diagram, 3 -> 4 ->5, upward traversal through the stack, how do we know? 

    previous node = current node's right child, in other words, right child is just visited, it is root node's turn to pop out. 

2. Please write down steps of post order traversal in the above diagram: 

In the above diagram, 

step 1:  9 -> stack

        2:  5 -> stack

        3.  1->stack

        4. check stack is empty or not, 

        5.  not empty, peek the stack, the node N, see if previous is N's right child or not

            not true

        6. Pop node with value 1

        7. Peek stack's top node, and see if previous visited node is current node's right child or not

            it is not

        8. Check its right child existing or not

        9. It is existing, then, add current node to stack, repeat while loop...

 Julia could not explain it very clearly, she spent over 2 hours to get lost in the code, played with simple test cases: 

Null tree, tree with one node, tree with two nodes, tree with only left child, tree with only right child. 

She just noticed that it is easy to get complicated while loop, much more complicated code, and then, spin inside and waste time. 

It is better to delete everything and then start it from beginning. 

3. Go through the code and explain what you learn through the practice:

Answer: 

To make solution simple as possible, three things need to be taken care of:

1. First, downward, push nodes to stack, like 9->5->1, leftmost nodes to the stack, continuously push them to the stack. 

2. Second, need to know when to pop out to add traversal list

1 to the list, 

then, 5 is the top of stack, smart enough to know that it is turn to visit right child. 

3. Third, need to take care of upward pop up, like 7->8->9

When you design the process, leave "set stack's top node's right child to runner" as last. 

Then, take care of upward pop up process, it is a while loop, not a if checking - one time deal. 

         Like the above diagram, let 7 ->8->9 three continuously pop out. 

         And then, check the stack is empty or not, if it is empty, break the while loop. 

For example, the last one, root node 9 is popped out, then, break the outside while loop, terminate the loop, otherwise, it is a dead loop. 

         Last, stack is not empty, we need to set stack's top node's right node as runner node, let iteration repeats. 

Julia learned that in order to produce working code with no bug, take a lot of practice. 

line 68: while (stack.Count > 0 && (stack.Peek().right == null || stack.Peek().right == runner))

                {

                    runner = stack.Pop();

                }

                if (stack.Count == 0)

                {

                    break;

                }

                else

                {

                    runner = stack.Peek().right;

                }

4. What are most difficult to learn through your practice? 

Answer:

When the node is added to post order traversal list, in the above diagram, 

Node with value 1 (denoted as short hand N1) is added to post order traversal output list, then, stop output, add more nodes (N4, N2) into stack;

N2 is added to post order traversal, and then, stop output, add N3 in the stack; 

N3 is added to post order traversal output list, then N4, then N5, 3 in a row to add output traversal list. 

N1, N2, N3 can generalized to upward output process, N1, N2 are special case, only 1 in row, N3 starts a 3 in a row. 

Every node is added to stack, N9, N5, N1, 3 in a row to add into the stack; then, N4, N3, two in a row, so adding nodes to the stack is always in a process - downward, left most nodes in a row process. 

So, the design of function now becomes the following 4 steps:

1. Set up a while loop, work on runner node, use extra variable called previous visited node, prev

2. Take care downward push into stack in a row process. 

3. Take care upward pop out from stack in a row process. 

4. If the stack is empty, terminate the while loop. 

5. If the stack is not empty, set runner as stack's top node's right child, let while loop takes care next iteration. 

One more note, the upward pop out from stack in a row process, 3 conditions to check, first, the stack is not empty, and then, stack top node's right child is null (For node N1), or stack top node's right child is previous node. 

Based on the above analysis - 3 conditions, let us write down in one line of code:

while(stack.Count > 0 && (stack.Peek().right == null || stack.Peek().right == prev)  <- first try, it is wrong! 

second writing: 

while(stack.Count > 0 && (stack.Peek().right == null || stack.Peek().right == runner) 

The study code Julia chose is so good, even previous node variable is not needed to be declared! 

https://github.com/douglasleer/LeetCode-Java-Solutions/blob/master/236.lowest-common-ancestor-of-a-binary-tree.java

Julia spent 2 days to work on this algorithm, felt very down struggling with complicated while loop code, gave up after 3+ hours. Come back again with more warm ups, with a bug - out-of-index, and then, continuously test the code, write down ideas. 

5. What are fun part? 
Julia learns to teach herself algorithm very struggling on this algorithm, take more than 8 hours, she likes to focus on code; always work on code, play with code, get hands dirty, frustrated, add more test cases. She finds out playing part is fun like sports playing.

Leetcode 236: Lowest common ancestor in binary tree

April 25, 2016

Study the code:
https://github.com/douglasleer/LeetCode-Java-Solutions/blob/master/236.lowest-common-ancestor-of-a-binary-tree.java

Julia's C# warm up practice:
1. using Stack class ToArray API, keep the iterator order - stack output order: (5/21/2016)
https://gist.github.com/jianminchen/2bec8a70ef520e715240a226c01c7371

Read Stack class APIs:
https://msdn.microsoft.com/en-us/library/415129w1(v=vs.110).aspx

2. Use List.AddRange(Stack), still keep the stack iterator order
https://gist.github.com/jianminchen/754f45023f60992211cb34bef6d6254f


Compared to Java Stack class APIs later.

Question and answer:

1. What do you learn through the study of the code?

The code is using Binary Tree post order traversal method, and then, to find node p and q common ancestor, work on the stack, get list of nodes from root node to p, same to q, and then, find the common ancestor.

Blog:
http://juliachencoding.blogspot.ca/2015/08/tree-algorithms-review.html

Review:
Post order traversal iterative
https://github.com/jianminchen/leetcode-tree/blob/master/TreeDemo.cs

Write a C# version using exactly same idea.