285. Inorder Successor in BST

Problem:

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

Analysis:

4/24/2018 update:
It's BST version of binary search.

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode res = null;
        while (root != null) {
            if (root.val> p.val) {
                res = root;
                root = root.left;
            } else 
                root = root.right;
        }
        return res;
    }
}

Create a flag, set to true if found p. If flag is true, the current node is the successor of p.

Solution:

 /**  
  * Definition for a binary tree node.  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 class Solution {  
   public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {  
     TreeNode suc = null;  
           Stack<TreeNode> stack = new Stack<>();  
           boolean found = false;  
           while (!stack.isEmpty() || root != null) {  
                if (root != null) {  
                     stack.push(root);  
                     root = root.left;  
                } else {  
                     TreeNode temp = stack.pop();  
                     if (found) {  
                          suc = temp;  
           return suc;  
                     }   
                     if (p == temp) {  
                          found = true;  
                     }  
         root = temp.right;  
                }  
           }  
           return suc;  
   }  
 }