Tree algorithms review

August 23, 2015

Here is the list of tree questions worked on:

1. Lowest common ancestor in Binary Tree (January 6, 2016 - Leetcode question: 236 medium)

https://github.com/jianminchen/LowestCommonAncestorInBinaryTree/blob/master/LowestCommonAncestorB.cs

Lowest common ancestor in Binary Search Tree (January 6, 2016 - Leetcode question: 235 easy)
https://github.com/mengli/leetcode/blob/master/LowestCommonAncestorOfaBinarySearchTree.java

https://github.com/jianminchen/Leetcode_C-/blob/master/235LowestCommonAncestorBSearchTree.cs

https://github.com/jianminchen/Leetcode_C-/blob/master/235LowestCommonAncestorBinarySearchTree.cs

2. Leetcode 102: Binary tree level order traversal

a few of implementations:

https://github.com/jianminchen/BTreeLevelOrderTraversal

January 7, 2016 review
https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal4.cs

3. C# files:

TreeDemo.cpp

  Pre Order Traversal

  In Order Traversal

  Post Order Traversal

  Breadth First Traversal

  Breadth First Traversal Iterative

 Pre Order Traversal Iterative

 Post Order Traversal Iterative*

 In Order Traversal Iterative (A, B two versions)

 Count One Child Node

 Recover Binary Tree

 Invert Binary Tree

 Invert Binary Tree Iterative

 --

Tree Post Order Iterative

Tree In order Iterative

https://github.com/jianminchen/leetcode-tree

4. Tree Max Path Sum

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

5. Linked List To Binary Search Tree

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

6. Zigzag order traversal of a binary Tree

http://juliachencoding.blogspot.ca/2015/06/leetcode-zigzag-order-traversal-of.html

7. Maximum Binary Tree Path Sum

How to come out the idea using max value cross root? Cannot recall the idea. 
Read the blog again (8/25/2015):
http://blog.unieagle.net/2012/12/09/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Abinary-tree-maximum-path-sum/

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

The problem can be extended to  a tree, not just a binary tree. The solution is here:
http://juliachencoding.blogspot.ca/2015/07/itint5-tree-maximum-path-sum.html

8. ININT5: tree maximum path sum

http://juliachencoding.blogspot.ca/2015/07/itint5-tree-maximum-path-sum.html

9. Binary Tree Maximum Distance, diameter of binary

http://juliachencoding.blogspot.ca/2015/06/binary-tree-maximum-distance-diameter.html

10. Morris Inorder Traversal

http://juliachencoding.blogspot.ca/2015/06/morris-inorder-traversal-binary-tree.html

11. Convert sorted List to binary search tree (I) (Leetcode question: No. 109)

http://juliachencoding.blogspot.ca/2015/06/leetcode-convert-sorted-list-to.html

12. Convert sorted list to binary search tree (II) (over 3 hours debugging to find a bug) (Leetcode question: No. 109)

http://juliachencoding.blogspot.ca/2015/06/leetcode-sorted-list-to-binary-search.html

August 23, 2015

It is so good to have chance to review post order traversal iterative solution. So, Julia had chance to read more about the problem, understand another solution using space O(log(n)), use a prev variable to keep track of the previously-traversed node. 

Also, she had chance to work out using two stacks solution for post order traversal iterative solution.

Like this, First stack,       root -> left child -> right child, the order of getting into first stack, 

however, second stack, root-> right child -> left child, the order of getting into second stack. 

since left, right child both get into the first stack, then, pop out two of them in reverse order. 

* Read the following blog to help understand post order traversal iterative

http://articles.leetcode.com/2010/10/binary-tree-post-order-traversal.html

C# implementation of post order traversal iterative solution, using prev variable to help:

https://github.com/jianminchen/leetcode-tree/blob/master/TreePostOrderIterative_PrevVarirable.cs

August 24, 2015

13. Convert sorted list to binary search tree (No. 109)
Read the following blogs:
http://articles.leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

C#, bottom up, time O(n), space O(log n) solution:
https://github.com/jianminchen/Leetcode_C-/blob/master/109ConvertSortedListToBinarySearchTreeB.cs

C#, top down, time O(n^2), space O(long n) solution:

worked on code 2 times, first time, the calculation is kind of messy, then, worked on Leetcode question 108, get the idea to make it more simple; tips like len/2 only shows once, afterwards, use m instead. Just need to improve coding, think to make it more abstract, simple.

https://github.com/jianminchen/Leetcode_C-/blob/master/109ConvertSortedListToBinarySearchTreeC.cs

14. Convert sorted array to binary search tree (No. 108)

https://github.com/jianminchen/Leetcode_C-/blob/master/108ConvertSortedArrayToBinarySearchTree.cs

August 27, 2015
Leetcode Tree questions (29 questions):

94 Binary Tree Inorder Traversal 95 Unique Binary Search Trees II 96 Unique Binary Search Trees 98 Validate Binary Search Tree 99 Recover Binary Search Tree 100 Same Tree 101 Symmetric Tree 102 Binary Tree Level Order Traversal 103 Binary Tree Zigzag Level Order Traversal 104 Maximum Depth of Binary Tree https://github.com/jianminchen/Leetcode_C-/blob/master/104MaximumDepthOfBinaryTree.cs 105 Construct Binary Tree from Preorder and Inorder Traversal 106 Construct Binary Tree from Inorder and Postorder Traversal 107 Binary Tree Level Order Traversal II 108 Convert Sorted Array to Binary Search Tree 109 Convert Sorted List to Binary Search Tree 110 Balanced Binary Tree 111 Minimum Depth of Binary Tree 114 Flatten Binary Tree to Linked List 124 Binary Tree Maximum Path Sum 144 Binary Tree Preorder Traversal 145 Binary Tree Postorder Traversal 156 Binary Tree Upside Down  173 Binary Search Tree Iterator 199 Binary Tree Right Side View 208 Implement Trie (Prefix Tree) 222 Count Complete Tree Nodes 226 Invert Binary Tree 235 Lowest Common Ancestor of a Binary Search Tree 236 Lowest Common Ancestor of a Binary Tree 250 Count Univalue Subtrees
More practice using C#: August 28, 2015
104 Maximum Depth of Binary Tree https://github.com/jianminchen/Leetcode_C-/blob/master/104MaximumDepthOfBinaryTree.c
95 Unique Binary Search Trees II
https://github.com/jianminchen/Leetcode_C-/blob/master/95UniqueBinarySearchTreeII.cs 98 Validate Binary Search Tree Blogs to read:  http://blog.csdn.net/likecool21/article/details/23271621 https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning favorite blog about this problem: http://huntfor.iteye.com/blog/2070278
solutions included in C# practice:  1. recursive, time O(n), using beta-alpha pruning?  2. recursive, use long Max value / min Value instead of int's to avoid the bug  3. use inorder traversal output to help checking BST  4. same as 3, value TreeNode variable  5. sames as 3,  6. same as 3,  7. same as 3, but use iterative solution  8. Great analysis, brute force solution, time complexity O(n^2) vs beta-alpha pruning time O(n)
https://github.com/jianminchen/Leetcode_C-/blob/master/98ValidateBinarySearchTree.cs 99 Recover Binary Search Tree - August 30, 2015 read blogs: http://www.lifeincode.net/programming/leetcode-recover-binary-search-tree-java/ http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html C# implementations: https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoverBinarySearchTree.cs https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoverBinarySearchTreeB.cs work on extracting small functions, and then, understand the algorithm better. https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoveryBinarySearchTree_C.cs 100 same tree blogs to read: http://blog.csdn.net/linhuanmars/article/details/22839819 http://www.cnblogs.com/lautsie/p/3247097.html http://www.cnblogs.com/TenosDoIt/p/3440753.html julia's implementation in C# https://github.com/jianminchen/Leetcode_C-/blob/master/100SameTree.cs
Sept. 5, 2015 Morris order post order traversal blogs to read: http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html C# implementation: https://github.com/jianminchen/MorrisOrder/blob/master/MorrisPostOrder.cs Morris order in order traversal https://github.com/jianminchen/MorrisInOrderTraverse/blob/master/Program.cs
Sept. 7, 2015 101 Symmetric Tree this one is good to follow use queue http://www.cnblogs.com/TenosDoIt/p/3440729.html LinkedList - as queue - Java http://www.cnblogs.com/springfor/p/3879595.html julia's practice: (Sept. 8, 2015) https://github.com/jianminchen/Leetcode_C-/blob/master/101SymmetricTreeA.cs 105 Construct binary tree from preorder and inorder traversal 106 Construct binary tree from inorder and postorder traversal http://siddontang.gitbooks.io/leetcode-solution/content/tree/construct_binary_tree.html C# practice: https://github.com/jianminchen/Leetcode_C-/blob/master/106ConstructuBTreeFromInorderPostOrderTraversal.cs
second implementation using C#: https://github.com/jianminchen/Leetcode_C-/blob/master/106ConstructBTreeFromInOrderPostOrderTraversal_B.cs
Sept. 13, 2015 208 Implement Trie (prefix tree) blogs: http://pisxw.com/algorithm/Implement-Trie-(Prefix%20Tree).html http://www.jyuan92.com/blog/leetcode-implement-trie-prefix-tree/
August 25, 2015 January 5, 2015 Preorder traversal of ternary tree
https://github.com/jianminchen/TreeAlgorithms/blob/master/ternaryTreeTraversal.cs

  More reading about ternary tree:
https://en.wikipedia.org/wiki/Ternary_search_tree