Leetcode/F家微软-- 285. Inorder Successor in BST

285. Inorder Successor in BST

• Difficulty: Medium

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
https://leetcode.com/problems/inorder-successor-in-bst/  

Pocket Gems Microsoft Facebook

*Inorder successor in bst: the 1st value great than current value 
That node is the smallest node in p' right branch, if not found can either be p's parent else null .
思路1： Find p in the tree, use a stack to store the path. 2 cases
1. if the right node is not empty，print the leftmost leaf of rightnode or itself.
2. if the right node is null, print the 1st value in stack that is greater than curr.val
else not found return null.
Complexity: time O(n) - store path. space O(n)

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null)return root;
        Deque<TreeNode> st = new LinkedList<TreeNode>();
        TreeNode curr = root;
        // Find the target node while saving the path
        while(curr!=p){
            st.push(curr);
            if(curr.val > p.val){
                curr = curr.left;
            }else{
                curr = curr.right;
            }
        }
        // if curr has right node, find the leftmost of right node(or itself), is the successor
        if(curr.right != null){
            curr = curr.right;
            while(curr.left != null){
                curr = curr.left;
            }
            return curr;
        }else{
        // if curr has no right node, find the 1st node in stack that val > curr.val  
            while(!st.isEmpty()){
                if(st.peek().val>curr.val)return st.pop();
                st.pop();
            }    
            // 如果栈都pop空了还没有比目标节点大的，说没有更大的了
            return null;
        }
    }
}

思路2： use dfs
参考： https://discuss.leetcode.com/topic/25076/share-my-java-recursive-solution/13

 When the code runs into the else block, that means the current root is either p's parent or a node in p's right branch.

If it's p's parent node, there are two scenarios: 1. p doesn't have right child, in this case, the recursion will eventually return null, so p's parent is the successor; 2. p has right child, then the recursion will return the smallest node in the right sub tree, and that will be the answer.

If it's p's right child, there are two scenarios: 1. the right child has left sub tree, eventually the smallest node from the left sub tree will be the answer; 2. the right child has no left sub tree, the recursion will return null, then the right child (root) is our answer.

关键字： recursion
Complexity : time O(logn); space O(logn) for stack,           

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null){ return root;}
        if(root.val<=p.val){//利用BST性质
            TreeNode right = inorderSuccessor(root.right,p);//successor in the right subtree
            return right;
        }else{
            TreeNode left = inorderSuccessor(root.left,p);//looking for p in the left subtree
            return left != null?left:root;//null case: when leftmost leaf
        }
    }
}

Predecessor

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null){ return root;}
        if(root.val>=p.val){//利用BST性质
            TreeNode left = inorderSuccessor(root.left,p);
            return left;
        }else{
            TreeNode right = inorderSuccessor(root.right,p);//右叶，打印中叶或root
            return right != null?right:root;
        }
    }
}