Binary Tree Inorder traversal - Iterative solution - warm up practice

May 25, 2016 Review binary tree inorder iterative solution, add some test cases. Julia C# practice code of binary tree C# practice Questions and Answers: 1. How is the practice of inorder traversal iterative solution? Julia compared to the other solution, line 354 - line 372, inOrderIterative_B https://github.com/jianminchen/leetcode-tree/blob/master/TreeDemo.cs and chose this one to practice: C# practice She wrote some comment to argue that the solution is very efficient and no redundant code. She likes to use reasoning and analysis to help her structure the function. Here are her analysis:           1. First, argue that line 88, why to check "if stack is empty, break the while loop" before outputting any node in the stack. Otherwise, if the stack is empty, then, line 91: execution run time error. 2. Second, argue that output of inorder traversal nodes is not in inner loop. If there are more than 1 in a row to output, then the outer while loop (line 79) will take care of it.       3. Third, argue that line 94: runner = runner.right; It does not matter that right child exists or not, line 81 will take care of null.  Complete one iteration - Push nodes into stack, then first node in inorder is on the top of stack, If stack is empty, break; otherwise, ready to pop top one from the stack, and then, move runner to its right child. Follow up after 12 months March 27, 2017 Read the blog and think about the better presentation, more readable.  Write another C# practice, and post a question about binary tree inorder traversal (iterative solution) for code review.

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.

Leetcode 331: Verify Preorder serialization of a Binary Tree

 Feb. 8, 2016

Serialization of a binary tree, great algorithm to review.

331. Verify Preorder serialization of a Binary Tree

One way to serialize a binary tree is to use pre-oder traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where# represents a null node.

idea: Use stack


Here is the blog she starts to read.

  http://bookshadow.com/leetcode/

  https://www.hrwhisper.me/leetcode-algorithm-solution/

  http://www.cnblogs.com/grandyang/p/4606334.html

  http://www.cnblogs.com/EdwardLiu/tag/Leetcode/

 To be continued. 

Leetcode 314: Binary Tree Vertical Order Traversal

January 16, 2016 

First time after 9 years, I installed Eclipse, J2SE, and then, set up Java developer IDE Eclipse, ran the first Java program. Such a great ride to enjoy Java programming. Still remember that in 2006 - 2007, spent over 10 hours daily to read/ run/ maintain software using Java programming language, when I worked for a small startup called Siva Corp Inc. in the city of Delray Beach, Florida, USA. 

Just bring all my good memory back about programming using Java.


http://buttercola.blogspot.ca/2014/09/leetcode-n-queens.html

Leetcode 314:
https://github.com/jianminchen/Leetcode_C-/blob/master/BinaryTreeVerticalOrderTraversal_314.java

Another blog using C++,

http://buttercola.blogspot.ca/2014/12/facebook-print-binary-tree-in-vertical.html

Leetcode 124: Maximum binary tree path sum

July  4, 2015

Problem statement:

Given a binary tree, find the maximum path sum. 

The path may start and end at any node in the tree. 

For example: 

Given the below binary tree, 

  1 

 /  \ 

2   3 

Return 6.

Blogs to read:

http://blog.unieagle.net/2012/12/09/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Abinary-tree-maximum-path-sum/

http://shanjiaxin.blogspot.ca/2014/02/binary-tree-maximum-path-sum-leetcode.html

http://bangbingsyb.blogspot.ca/2014/11/leetcode-binary-tree-maximum-path-sum.html

http://jane4532.blogspot.ca/2013/09/binary-tree-maximum-path-sumleetcode.html

原来这讲解很清楚:

http://www.cnblogs.com/yuzhangcmu/p/4172855.html

The best readable code, and perfect to follow for this problem:

https://github.com/xiaoxq/leetcode-cpp/blob/master/src/BinaryTreeMaximumPathSum.cpp

Julia's C# practice.

https://github.com/jianminchen/BinaryTreeMaxPathSum/blob/master/Program.cs

https://github.com/jianminchen/Leetcode_C-/blob/master/124BinaryTreeMaximumPathSum.cs

Extension problem:

https://github.com/AnnieKim/ITint5/blob/master/013_%E6%A0%91%E4%B8%AD%E6%9C%80%E5%A4%A7%E8%B7%AF%E5%BE%84%E5%92%8C.cpp

February 3, 2016

Review the algorithm, need to figure out how to make this algorithm easy to remember, recall, write without a bug.

Good analysis from the blog (http://www.cnblogs.com/yuzhangcmu/p/4172855.html):

计算树的最长path有2种情况：

1. 通过根的path.

  (1)如果左子树从左树根到任何一个Node的path大于零，可以链到root上

  (2)如果右子树从右树根到任何一个Node的path大于零，可以链到root上

2. 不通过根的path. 这个可以取左子树及右子树的path的最大值。

所以创建一个inner class:

记录2个值：

1. 本树的最大path。

2. 本树从根节点出发到任何一个节点的最大path.

注意，当root == null,以上2个值都要置为Integer_MIN_VALUE; 因为没有节点可取的时候，是不存在solution的。以免干扰递归的计算

http://www.cnblogs.com/yuzhangcmu/p/4172855.html

Practice using this class as return type:

private class ResultType { int singlePath; int maxPath; ResultType(int singlePath, int maxPath) { this.singlePath = singlePath; this.maxPath = maxPath; } Read more blogs: http://buttercola.blogspot.ca/2014/08/leetcode-binary-tree-maximum-path-sum.html Discussion of global variable - max value - Julia likes the discussion  https://leetcode.com/discuss/14190/accepted-short-solution-in-java

Microsoft phone screen | Binary Tree: Write a function to return count of nodes in binary tree which has only one child.

June 8, 2015

我最喜欢的一道算法题目, 我写了七八行.　你准备了几行?　

去年我才知道这道题可以用二行代码. 2014年七月, 第一次世界上最强的算法高手耐心地开导我, 教会我如何优化代码的, argue, change, using logic reasoning and try to make it minimal. 假想代码bug, 开始改; 然后, 试图解释清楚, 自己的想法.

讨论的要点:
1. Local variable in each recursive function
2. Redundancy code
3. If statement, how many if statement in the function
4. How to argue that the code will not have bugs? Can you simplify the code?
5. Make the code simple as possible, no way to hide any bugs
6. Base case discussion
7. Discussion if null checking is needed to call the function.
8. Use a global variable to store the count.
9. Function arguments - what arguments are needed.

2015年初, 决定从Java Script 学习, 转到算法, C#, Leetcode;  先练习最基本的问题.

Github for source code:

https://github.com/jianminchen/BinaryTreeOneChild/blob/master/Program.cs

只有一个孩子, 可以表示为一句话:　 (node.left!=null) != (node.right!=null)

Follow up

Feb. 15, 2019
Here is the link of my practice.

Follow up 

Nov. 1, 2023

I remembered that I had a phone screen from Microsoft. The interviewer was a principle engineer from Microsoft, and he coached me through the phone screen interview how to write an elegant solution using two lines of code. 

Actually I spent near 30 minutes to work with him, and I tried to write a broken solution. 

Leetcode: zigzag order traversal of binary tree

One more C# practice on level order traversal. So excited to read my past practice in 2015, April 29. Cheers! 

April 29, 2015 

I Spent a few hours to study the question. The website I read:

http://www.jiuzhang.com/solutions/binary-tree-zigzag-level-order-traversal/

One thing I do not like is to use two while loop, and since it makes me wonder how to make it more simple and readable.

This is a better solution, I like it more:

http://rleetcode.blogspot.ca/2014/02/binary-tree-zigzag-level-order.html

Here is C# code I write and test on April 29, 2015:

https://github.com/jianminchen/zigzagOrderTraversal/blob/master/Program.cs

Follow up 

May 3, 2018

I spent over 30 minutes to review the C# code writting in 2015. I am not happy about the coding style, and also the code is not easy to read. I need to debug the code, and then update readable variable names, and understand how to apply stack to store nodes for each level.


Here is the C# code I ran and passed all test cases.