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!
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.
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.
