package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

/**285. Inorder Successor in BST

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. */
public class _285 {

    /**credit: https://discuss.leetcode.com/topic/25698/java-python-solution-o-h-time-and-o-1-space-iterative
     The inorder traversal of a BST is the nodes in ascending order.
     To find a successor, you just need to find the smallest one that is larger than the given value since there are no duplicate values in a BST.
     It's just like the binary search in a sorted list.

     The time complexity should be O(h) where h is the depth of the result node.
     succ is a pointer that keeps the possible successor.
     Whenever you go left the current root is the new possible successor, otherwise the it remains the same.

     Only in a balanced BST O(h) = O(log n). In the worst case h can be as large as n.
     */
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = null;
        while (root != null) {
            if (p.val < root.val) {
                successor = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return successor;
    }

}

@@ -78,16 +78,92 @@
 eNode;%0A%0A
+import java.util.Iterator;%0Aimport java.util.Map;%0Aimport java.util.TreeMap;%0A%0A
 /**285. 
@@ -391,19 +391,71 @@
  %7B%0A%0A    
-/**
+public static class Solution1 %7B%0A        /**%0A         * 
 credit: 
@@ -549,24 +549,30 @@
 erative%0A    
+     *
  The inorder
@@ -628,16 +628,22 @@
 er.%0A    
+     *
  To find
@@ -781,16 +781,22 @@
 ST.%0A    
+     *
  It's ju
@@ -839,21 +839,41 @@
 d list.%0A
-%0A
     
+     * %3Cp%3E%0A         *
  The tim
@@ -941,24 +941,30 @@
 t node.%0A    
+     *
  succ is a p
@@ -1009,16 +1009,22 @@
 or.%0A    
+     *
  Wheneve
@@ -1120,21 +1120,41 @@
 e same.%0A
-%0A
     
+     * %3Cp%3E%0A         *
  Only in
@@ -1233,19 +1233,27 @@
 n.%0A     
+   
+ 
 */%0A
+    
     publ
@@ -1306,24 +1306,28 @@
 eeNode p) %7B%0A
+    
         Tree
@@ -1357,16 +1357,20 @@
         
+    
 while (r
@@ -1380,24 +1380,28 @@
  != null) %7B%0A
+    
             
@@ -1440,16 +1440,20 @@
         
+  
+  
 successo
@@ -1462,16 +1462,20 @@
 = root;%0A
+    
         
@@ -1512,16 +1512,20 @@
         
+   
+ 
 %7D else %7B
@@ -1525,16 +1525,20 @@
  else %7B%0A
+    
         
@@ -1568,32 +1568,36 @@
 ht;%0A            
+    
 %7D%0A        %7D%0A    
@@ -1582,34 +1582,42 @@
       %7D%0A        
+ 
-%7D%0A
+   %7D%0A    
         return s
@@ -1626,16 +1626,1065 @@
 cessor;%0A
+        %7D%0A    %7D%0A%0A    public static class Solution2 %7B%0A        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) %7B%0A            TreeMap%3CInteger, TreeNode%3E map = new TreeMap%3C%3E();%0A            inorderTraversal(root, map);%0A            Iterator%3CMap.Entry%3CInteger, TreeNode%3E%3E iterator = map.entrySet().iterator();%0A            while (iterator.hasNext()) %7B%0A                Map.Entry%3CInteger, TreeNode%3E entry = iterator.next();%0A                if (entry.getValue() == p) %7B%0A                    if (iterator.hasNext()) %7B%0A                        return iterator.next().getValue();%0A                    %7D else %7B%0A                        return null;%0A                    %7D%0A                %7D%0A            %7D%0A            return null;%0A        %7D%0A%0A        private void inorderTraversal(TreeNode root, TreeMap%3CInteger, TreeNode%3E map) %7B%0A            if (root == null) %7B%0A                return;%0A            %7D%0A            inorderTraversal(root.left, map);%0A            map.put(root.val, root);%0A            inorderTraversal(root.right, map);%0A            return;%0A        %7D%0A
     %7D%0A%0A%7D

refactor 285