package lintcode.bst;

import fundamentals.tree.TreeNode;

/**
 */
public class MyBst {

    // 85-Insert Node in a Binary Search Tree
    public TreeNode insertNode(TreeNode root, TreeNode node) {
        if (root == null) return node;
        if (node.val < root.val) {
            root.left = insertNode(root.left, node);
        } else {
            root.right = insertNode(root.right, node);
        }
        return root;
    }

    public TreeNode insertNode_iterative(TreeNode root, TreeNode node) {
        TreeNode cur = root, par = null;
        while (cur != null) {
            par = cur;
            cur = (node.val < cur.val) ? cur.left : cur.right;
        }
        if (par == null) { // root is empty
            root = node;
        } else if (node.val < par.val) {
            par.left = node;
        } else {
            par.right = node;
        }
        return root;
    }

}

@@ -52,16 +52,68 @@
 eNode;%0A%0A
+import java.util.ArrayList;%0Aimport java.util.List;%0A%0A
 /**%0A */%0A
@@ -944,10 +944,1241 @@
 %0A    %7D%0A%0A
+    // Leetcode-285 Inorder Successor in BST%0A    // %22To find a successor, you just need to find the smallest one that is larger than the given value.%0A    // Since there are no duplicate values in a BST. It just like the binary search in a sorted list.%22%0A    public TreeNode inorderSuccessor(TreeNode root, TreeNode x) %7B%0A        TreeNode p = root, pre = null;%0A        while (p != null) %7B // Find lowest ancestor whose left child is ancestor of x too%0A            if (x.val %3C p.val) %7B%0A                pre = p;%0A                p = p.left;%0A            %7D else%0A                p = p.right;%0A        %7D%0A        return pre;%0A    %7D%0A%0A    // 11-Search Range in Binary Search Tree%0A    public List%3CInteger%3E searchRange(TreeNode root, int k1, int k2) %7B%0A        List%3CInteger%3E ret = new ArrayList%3C%3E();%0A        dfs(ret, root, k1, k2);%0A        return ret;%0A    %7D%0A%0A    private void dfs(List%3CInteger%3E ret, TreeNode root, int k1, int k2) %7B%0A        if (root == null) return;%0A        if (k1 %3C root.val) dfs(ret, root.left, k1, k2);%0A        if (k1 %3C= root.val && root.val %3C= k2) ret.add(root.val);%0A        if (root.val %3C k2) dfs(ret, root.right, k1, k2);%0A    %7D%0A%0A    // minimum, maximum, delete min, floor, ceiling, delete, rank, select refer to %3CAlgorithm 4e%3E%0A%0A
 %7D%0A

Implement my binary search tree