1. Binary Tree Inorder Traversal

2. Validate Binary Search Tree

3. Inorder Successor in BST

4. in-order successor with parent pointer

5. Binary Search Tree Iterator

6. Minimum Absolute Difference in BST

2. Validate Binary Search Tree

1. ResultType: min, max, isValid
2. in-order traversal, check values: need a ptr for the previous value
3. min & max: null

• 第二种方法一般可行，但是如果有duplicates的话就无法判断了，比如left <= root < right

    6        6
  /           \
6              6

第二个例子明显不符合条件，但是Inorder traversal是无法甄别的。

如果是strict bst，那就可以。

• 第三种方法实现起来超级简单的。问题是，我用的是Integer，如果root.val很大的话，就不能储存了。
  • O(n) time: touch all N nodes
  • O(log n) space: for a balanced tree. At most O(log n) recursive calls on the stack.

3. Inorder Successort in BST

4. in-order successor with parent pointer

leftmost child of right subtree / if doesn't have right subtree, then go up until right turn

public TreeNode inorderSucc(TreeNode n) {
    if (n == null) return root;
    if (n.right != null) {
        return getLeftMostChild(n);
    } else {
        TreeNoe parent = n.parent;
        //parent.right == n means n is larger than parent
        while (parent != null && parent.right == n) {
            n = parent;
            parent = parent.parent;
        }
        return parent;
    }
}

private TreeNode getLeftMostChild(TreeNode n) {
    while (n.left != null){
        n = n.left;
    }
    return n;
}