package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;

public class _285 {

    public static class Solution1 {
        /**
         * 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.
         * <p>
         * 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.
         * <p>
         * 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;
        }
    }

    public static class Solution2 {
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            TreeMap<Integer, TreeNode> map = new TreeMap<>();
            inorderTraversal(root, map);
            Iterator<Map.Entry<Integer, TreeNode>> iterator = map.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry<Integer, TreeNode> entry = iterator.next();
                if (entry.getValue() == p) {
                    if (iterator.hasNext()) {
                        return iterator.next().getValue();
                    } else {
                        return null;
                    }
                }
            }
            return null;
        }

        private void inorderTraversal(TreeNode root, TreeMap<Integer, TreeNode> map) {
            if (root == null) {
                return;
            }
            inorderTraversal(root.left, map);
            map.put(root.val, root);
            inorderTraversal(root.right, map);
            return;
        }
    }

}

@@ -95,24 +95,75 @@
 va.util.
-Iterator
+ArrayList;%0Aimport java.util.Iterator;%0Aimport java.util.List
 ;%0Aimport
@@ -934,20 +934,16 @@
 herwise 
-the 
 it remai
@@ -2472,32 +2472,32 @@
 ot.right, map);%0A
-
             retu
@@ -2517,10 +2517,837 @@
 %0A    %7D%0A%0A
+    public static class Solution3 %7B%0A        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) %7B%0A            List%3CTreeNode%3E inorder = new ArrayList%3C%3E();%0A            dfs(root, inorder);%0A            for (int i = 0; i %3C inorder.size() - 1; i++) %7B%0A                if (inorder.get(i) == p) %7B%0A                    return inorder.get(i + 1);%0A                %7D%0A            %7D%0A            return null;%0A        %7D%0A%0A        private List%3CTreeNode%3E dfs(TreeNode root, List%3CTreeNode%3E inorder) %7B%0A            if (root == null) %7B%0A                return inorder;%0A            %7D%0A            if (root.left != null) %7B%0A                dfs(root.left, inorder);%0A            %7D%0A            inorder.add(root);%0A            if (root.right != null) %7B%0A                dfs(root.right, inorder);%0A            %7D%0A            return inorder;%0A        %7D%0A    %7D%0A%0A
 %7D%0A

add a solution for 285