【第三轮】7.7-7.13 CareerCup 4.6

4.6 Write an algorithm to find the 'next' node (i.e., in-order successor) of a given node in a binary search tree. You may assume that each node has a link to its parent.

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】
1.一个节点有右孩子，则在中序遍历中，该节点的后继是它的右子树的最左节点。
2. 这个节点是它父亲的左孩子，则该节点的后继节点是它的父亲
3. 这个节点是它父亲的右孩子，则需要一直向上搜索，直到它们n-1代祖先是它第n代祖先的左孩子，则它的后继就是第n个祖先。如果一直搜索到根节点，也没有找到n-1代祖先是它第n代祖先的左孩子，则该节点是整个树的中序遍历中的最后一个节点，即它没有后继。
【时间复杂度】
O(h)(worst)——when the node is on the longer branch
【空间复杂度】
O(1)
https://github.com/donnice/donnice/blob/master/Q4_6
【Test case】
                        5                                                               
             2                  8                              
       1          4       7                                          
             3        
顺便我的代码里写了个getParent的接口，大家有兴趣可以参考下     

【解题思路】
There are two cases:
1. if the node has right child, then find the minimum element of the subtree rooted at the right of this node. By BST property, this is the successor of our node.
2. if node has no right subtree, then this node must be the maximum of a certain tree. So for the root of this tree, it should be left child of another node N or it is the root of the whole BST. if it is N, then N is our successor, otherwise there is no successor(since we are the right most node of the whole BST).
【时间复杂度】
O(h) (h means height of the tree)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/ryancooper/a87fb60f8f9b7865ecf1

【解题思路】
If node's right subtree is not null
        return minimum node of the right subtree
else
        return the first of the node's ancester who has the node in its left sub tree

【时间复杂度】
O(N) worst case

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/e5c39bbb553fca36f257

【解题思路】
1. if the node has a right child, return the leftmost node of its right subtree
2. else if the node is the left child of its parent, return its parent
3. else (the node is the right child of its parent) then keep searching upwards the tree until the situation of (2) is found

【时间复杂度】
O(h)


【空间复杂度】
O(1)


【gist link】
https://gist.github.com/happyWinner/e3a6f0601e611d5a59fb

【解题思路】
inorder 的下一个节点
1. 有右子结点的话，是右子结点的最左节点
2. 作为左枝上节点出现的根节点
3. 不是以上两者，就是 null
【时间复杂度】
O(H)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/JoyceeLee/0e0409af30f86a9af2de

【解题思路】
if current node has right child: search for the leftmost node in the right subtree and return that node
if not: search backwards until a node that is left child of its parent, return the parent; or until reach the root, return null.
【时间复杂度】
O(H)
worse case: O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/3febb995ce4af53c8f67
【test case】
this algorithm does not limit to binary search tree. applicable with any binary tree.

【解题思路】
the parent of root is null
(1) if node.right not null, the next node the the min of the right subtree or the leftmost of right subtree
(2) if node is in the parent's left subtree, the next node is the parent
(3) if node is in the parent's right subtree, go up and find the ancestor which is the left child of its parent, the next node is the ancestor's parent
【时间复杂度】
O(H) - height of the tree
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/iwilbert/5842b8f26cc9482fcca3

【解题思路】
(1) if node.has right child, return the right child
(2) else, if the node is on left of the parent, return the parent node
(3) if node is in parent's right, go up and find the ancestor which is the left child of its parent, the next node is the ancestor's parent
【时间复杂度】
O(H) - height of the tree
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/bitcpf/0f9a508eb9692a9362b2