[第二轮] 3/11-3/17 CareerCup 4.6

Write an algorithm to find the ‘next’ node (i.e., in-ordersuccessor) of a given node in a binary search tree. You may assume that eachnode has a link to its parent.

发帖规范:http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

solution A hard to explain..consider different situations
solution B 土办法:
dfs()
{
dfs(left)
print
dfs(right)
}

two case:
1. if node x has right child, the next node of x is the smallest node y in the subtree root from x.
2. if the right subtree of node x is empty and x has a successor y, then y is the lowest ancestor of x whose left child is also an ancestor of x
https://gist.github.com/chrislukkk/5174826

Should consider two scenarios: the node has right child or doesn't have. For the second scenario, there are also two sub-cases: the node is the left child or the right child.
https://github.com/moophis/careercup/blob/master/4.6.cpp

https://gist.github.com/ThunderXu/5176737
Consider whether the node has right child. if it hasn't right child, consider whether its a left child or right child, if it is a right child then consider its parent's parent...

https://github.com/1094401996/Ca ... rdot6/NextNode.java