1/17, Traversal on BST

如果没说，一定要make sure是不是BST，是的话通常要利用BST的性质。

左子树中所有节点小于root，右子树中所有节点大于root。
最左边的节点是BST的最小值，最右边的是最大值。
对BST的inorder traversal会得到一个sorted结果。

Convert BST to Greater Tree

take advantage of the features of BST, define a global sum and calculate the aggregate sum from right child to left child.

class Solution {
    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        convert(root);
        return root;
    }

    private void convert(TreeNode cur) {
        if (cur == null) return;
        convert(cur.right);
        cur.val += sum;
        sum = cur.val;
        convert(cur.left);
    }
}

Inorder Successor in Binary Search Tree

这道题分两步。首先，通过while比较当前节点与给的节点，利用BST找到给的点。然后判断给的点是否有右子树，再分两种情况。

如果有右子树，就go deep left，找到这个点的右子树的最左边的点。
如果没有的话，说明这个点要么是叶节点(左/右)，要么有左子树。有没有左子树不重要，因为左子树已经被访问过了。只要看是左节点还是右节点，左节点就返回此节点的parent，右节点就返回它parent的parent，结果都存在successor里了。

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) return null;

        TreeNode successor = null;
        while (root != null && root.val != p.val) {
            if (root.val > p.val) {
                successor = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        // if p does not exist in tree
        if (root == null) return null;

        if (root.right == null) return successor;

        root = root.right;
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }
}

successor在往左走的时候，被赋成当前的节点，往右边走不会被更改。这样的话，如果是往右找到的节点没有右子树，返回的successor就是它parent的parent。如果是往左找到的节点没有右子树，返回的successor是parent。

再做这道题时，觉得很考察思路的缜密。如何一步步写branch case，优化代码的简洁性。

12/15复习注，另一种把所有节点用inorder traversal后放到array里面，再遍历找到给定点的下一个点，不是最优方法。

因为如果每次只走一边，时间复杂度是O(lgn)。而如果traversal的话，要O(n)，而且需要extra space。

2/1复习，what if the node isn't in the tree?

1/19补充，F，L，G都tag过的题，fake hard。

Binary Search Tree Iterator

这题本质就是inorder traversal，跟BST没半毛钱关系。思路是把模板分解成两个function，作为class的method，并把root和stack作为class的 attribute，实现一个API可以inorder traverse tree。

public class BSTIterator {

    Deque<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new LinkedList<>();
        // for (TreeNode t = root; t != null; stack.push(t), t = t.left);
        TreeNode t = root;
        while (t != null) {
            stack.push(t);
            t = t.left;
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode node = stack.pop();
        if (node.right != null) {
            TreeNode temp = node.right;
            while(temp != null) {
                stack.push(temp);
                temp = temp.left;
            }
        }
        return node.val;
    }
}

Kth Smallest Element in a BST

因为对BST中序遍历能得到一个sorted结果，节点是按升序被访问的。这样的话，每次pop掉stack的一个节点，就把k减去1，直到k等于0时就是要找的点。

## pay attention, corner case: clarify what if k > num of nodes in the tree

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;

        int i = 0;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            i++;
            TreeNode node = stack.pop();
            if (i == k) {
                return node.val;
            }
            cur = node.right;
        }
        return 0;
    }
}

套用inorder traversal的模板。

follow up: what if the BST is modified(insert / delete operations) often and you need to find the kth smallest frequently?

maintain a size = k 的 max heap, 一直有insert的时候好办，有delete而且删掉的node又在heap里就只好找一下inorder successor
另一个应对多次查询的好办法是augmented binary tree，第一次用O(n) 的时间统计记录一下每个 node左子树节点个数, 后面的每次查询就可以 O(height) 的时间搜索了。

Find Second Largest Element in a BST

这道题要在BST里找第二大的节点，所以要先找到最大的节点(最右边的点)，分两种情况考虑，一层一层剥开。

如果最右边的点没有左子树，那么第二大的点是最右边点的parent。
如果最右边的点有左子树，就接着找它左子树的最大的节点。

public class Solution {

    public TreeNode findSecondLargest(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode cur = root;
        while (cur != null) {
            if (cur.right != null && cur.right.right == null && cur.right.left == null) {
                // cur.right is largest
                return cur;
            }
            else if (cur.right == null && cur.left != null) {
                // cur is the largest
                return findLargest(cur.left);
            }
            cur = cur.right;
        }
        return cur;    // pay attention, return None if root has no children
    }

    private TreeNode findLargest(TreeNode node) {
        while (node.right) {
            node = node.right;
        }
        return node;
    }
}

迭代第一个if case的逻辑，每次得先判断是否有右节点，有的话才能利用右节点试探下面的节点。能进入第二个elif case的话，说明此时访问到了最大节点，要检查有它没有左子树。

Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target. (also needs to clarify)

12/18复习补充，利用BST，每次往左/往右走都move close to the target，时间复杂度O(lgn)。

class Solution {
    public int closestValue(TreeNode root, double target) {
        if (root == null) return -1;

        int min = root.val;
        while (root != null) {
            if (Math.abs(target - root.val) < Math.abs(target - min)) {
                min = root.val;
            }
            if (target > root.val) {
                root = root.right;
            } else if (target < root.val) {
                root = root.left;
            } else {
                break;
            }
        }
        return min;
    }
}

Verify Preorder Sequence in Binary Search Tree

note: preorder sequence, 给定array如5(123)(678)，第一个元素一定为root，后面的比root小的连续序列为左子树，比root大的连续序列为右子树。左右子树可以为空，但是不能违反BST子树性质。所以如果> root的连续数组后面又出现了< root的元素，一定是false.

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null) return true;
        return verify(preorder, 0, preorder.length - 1);
    }
    private boolean verify(int[] preorder, int start, int end) {
        if (end - start <= 1) return true;

        int rootVal = preorder[start];
        int index = start + 1;
        while (index <= end && preorder[index] < rootVal) {
            index++;
        }

        while (index <= end) {
            if (preorder[index] < rootVal) {
                return false;
            }
            index++;
        } 
        return verify(preorder, start + 1, index - 1) &&
            verify(preorder, index, end);
    }
}

Insert Node in a Binary Search Tree

插入一个节点，要保持BST的性质。用while循环来比较当前cur和给定node的值，决定往左还是往右走，记录每次的cur值，当cur为空时退出循环。然后再比较node和last cur，决定插左/插右。

走了一半的树，时间复杂度O(lgn)。

迭代 ✔️
递归 ✔️

    public TreeNode insertNode(TreeNode root, TreeNode node) {
        // write your code here
        if (root == null) return node;
        TreeNode cur = root, parent = null;
        while (cur != null) {
            parent = cur;
            if (cur.val > node.val) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        if (parent.val < node.val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        return root;
    }

1/26更新，recursive，实际上是保存了上一步的parent。递归出口也适用于空节点的情况。

class Solution:
    def insertNode(self, root, node):
        if not root:
            return node

        if root.val < node.val:
            root.right = self.insertNode(root.right, node)

        elif root.val > node.val:
            root.left = self.insertNode(root.left, node)

        else:
            return # node exists in the tree

        return root

1/28补充， remaining questions are all lintcode, to review in future....

Remove Node in Binary Search Tree

递归 ✔️

time complexity 等于height of BST - O(lgn)

class Solution:
    def removeNode(self, root, value):
        if not root:
            return None  ## the root is empty, or the value doesn't exist in the tree 

        elif root.val > value:
            root.left = self.removeNode(root.left, value)

        elif root.val < value:
            root.right = self.removeNode(root.right, value)

        else:  ## get the node to be deleted 
            if not root.left and not root.right:
                root = None

            elif not root.left: ## pay attention use 'not'
                root = root.right

            elif not root.right:
                root = root.left

            else:
                min_node = self.findMin(root.right)
                root.val = min_node  ## copy the value of node, otherwise, copy a node may get a subtree 
                root.right = self.removeNode(root.right, min_node)

        return root  ## return a node

    def findMin(self, root):
        while root.left:
            root = root.left

        return root.val  ## pay attention, return the value of node, not node itself

思路是先通过递归找到要删的节点，再分三种情况。

case1: No children。把该node赋为None。

case2: One child。直接把child node copy过去，相当于删除了node。

case3: Two children。稍微复杂一点，先找到右子树的最小node(或者是左子树的最大node)，把该node的值赋给当前要删除的node，再删掉子树里重复了的最小node。

Search Range in Binary Search Tree

在BST里找到所有值在某个范围内的节点，按升序返回。方法是遍历整棵树，比较每个点，如果在范围内就push进res。两边都走，因为如果某个点在范围内，那么它的左子树和右子树中，都可能存在满足条件的点。最后要排序，时间复杂度是O(nlgn) on average。

class Solution:
    def searchRange(self, root, k1, k2):
        if not root:
            return []

        res, nodes = [], [root]
        while nodes:
            cur = nodes.pop()
            if cur.val >= k1 and cur.val <= k2:
                res.append(cur.val)
            if cur.left:
                nodes.append(cur.left)
            if cur.right:
                nodes.append(cur.right)

        return sorted(res)

1130再做这道题才恍然大悟，之前的方法不好，没有利用inorder traversal BST的优点。既然返回结果要求ascending，也是BST inorder traversal的顺序，就能省去结尾的排序步骤。优化的时间复杂度是O(n)。

class Solution:
    def searchRange(self, root, k1, k2):
        if not root:
            return []

        res = []
        nodes = []
        cur = root

        while cur or nodes:
            while cur:
                nodes.append(cur)
                cur = cur.left

            cur = nodes.pop()
            if cur.val >= k1 and cur.val <= k2:
                res.append(cur.val)

            elif cur.val > k2:
                break

            cur = cur.right

        return res

12/15复习注，如果对返回结果要求ascending order，那还是用第二种解法好。

2/2复习注，如果检查的节点值已经大于上限，就break，没必要再继续检查后面的了。

1/1，总结BST的Traversal问题。

对于BST的Traversal/Search，一种侧重于找到某个节点，直接利用BST节点值的比较来决定搜索的方向，这样效率更高。另一种是搜索有一定的顺序要求，或者要使搜寻结果有序，这样的话，利用BST的inorder traversal效率更高。

BST & BST traversal