package com.freetymekiyan.algorithms.level.medium;

import com.freetymekiyan.algorithms.utils.Utils.TreeNode;

/**
 * Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
 * <p>
 * Note: If the given node has no in-order successor in the tree, return null.
 * <p>
 * Company Tags: Pocket Gems, Microsoft, Facebook
 * Tags: Tree
 * Similar Problems: (M) Binary Tree Inorder Traversal, (M) Binary Search Tree Iterator
 */
public class InorderSuccessorInBST {

    /**
     * Tree, recursive.
     * In BST, root is the largest of left subtree, smallest of right subtree.
     * In-order successor is the smallest of all node's larger than p.
     * Then we can do a binary search like recurse to search the result.
     * <p>
     * If root's val <= p's, p's inorder successor is in the right subtree.
     * If root's val > p's, p's inorder successor can be in the left subtree.
     * Or is root itself if p is the largest in left subtree.
     */
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) {
            return null;
        }
        if (root.val <= p.val) {
            return inorderSuccessor(root.right, p);
        } else {
            TreeNode succ = inorderSuccessor(root.left, p);
            // If not found in left subtree, it's root.
            return succ == null ? root : succ;
        }
    }

    /**
     * Tree, iterative.
     * If p's val < root's, go to the left subtree and update root as a candidate result.
     * If p's val >= root's, go to the right subtree.
     */
    public TreeNode inorderSuccessorB(TreeNode root, TreeNode p) {
        if (p.right != null) { // Pruning, if p has right subtree.
            for (TreeNode cur = p.right; cur != null; cur = cur.left) {
                p = cur; // Successor will be leftmost leaf of right subtree.
            }
            return p;
        }
        TreeNode succ = null;
        while (root != null) {
            if (p.val < root.val) {
                succ = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return succ;
    }

}

@@ -776,20 +776,17 @@
  If 
-root
+p
 's val %3C
 = p'
@@ -785,13 +785,16 @@
 al %3C
-= p
+ root
 's
+ 
 , p'
@@ -817,22 +817,147 @@
 sor 
-is in the righ
+can be in the left subtree or is root.%0A     * %7C If left subtree recursive call returns null, return root.%0A     * %7C Otherwise return the lef
 t su
@@ -953,32 +953,39 @@
 the left subtree
+ result
 .%0A     * If root
@@ -979,16 +979,23 @@
     * If
+ p's %3E=
  root's 
@@ -1001,14 +1001,8 @@
  val
- %3E p's
 , p'
@@ -1017,38 +1017,34 @@
 r successor 
-can be
+is
  in the 
 left subtree
@@ -1023,35 +1023,36 @@
 essor is in the 
-lef
+righ
 t subtree.%0A     
@@ -1057,61 +1057,94 @@
   * 
-Or is root itself if p is the largest in left subtree
+Base case:%0A     * If root == null, root is null or reach a null node, just return null
 .%0A  
@@ -1294,95 +1294,25 @@
 if (
-root.val %3C= p.val) %7B%0A            return inorderSuccessor(root.right, p);%0A        %7D else
+p.val %3C root.val)
  %7B%0A 
@@ -1422,24 +1422,24 @@
  it's root.%0A
-
             
@@ -1469,24 +1469,93 @@
 oot : succ;%0A
+        %7D else %7B%0A            return inorderSuccessor(root.right, p);%0A
         %7D%0A  

update Inorder Successor in BST