package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

 Note:
 Given target value is a floating point.
 You may assume k is always valid, that is: k ≤ total nodes.
 You are guaranteed to have only one unique set of k values in the BST that are closest to the target.
 Follow up:
 Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

 Hint:

 Consider implement these two helper functions:
 getPredecessor(N), which returns the next smaller node to N.
 getSuccessor(N), which returns the next larger node to N.
 Try to assume that each node has a parent pointer, it makes the problem much easier.
 Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
 You would need two stacks to track the path in finding predecessor and successor node separately.

 */
public class _272 {

	public List<Integer> closestKValues(TreeNode root, double target, int k) {
		List<Integer> res = new ArrayList();

		Stack<Integer> s1 = new Stack(); // predecessors
		Stack<Integer> s2 = new Stack(); // successors

		inorder(root, target, false, s1);
		inorder(root, target, true, s2);

		while (k-- > 0) {
			if (s1.isEmpty()) {
				res.add(s2.pop());
			} else if (s2.isEmpty()) {
				res.add(s1.pop());
			} else if (Math.abs(s1.peek() - target) < Math.abs(s2.peek() - target)) {
				res.add(s1.pop());
			} else {
				res.add(s2.pop());
			}
		}

		return res;
	}

	// inorder traversal
	void inorder(TreeNode root, double target, boolean reverse, Stack<Integer> stack) {
		if (root == null) {
			return;
		}

		inorder(reverse ? root.right : root.left, target, reverse, stack);
		// early terminate, no need to traverse the whole tree
		if ((reverse && root.val <= target) || (!reverse && root.val > target)) {
			return;
		}
		// track the value of current node
		stack.push(root.val);
		inorder(reverse ? root.left : root.right, target, reverse, stack);
	}

}

@@ -158,16 +158,63 @@
 k;%0A%0A/**%0A
+ * 272. Closest Binary Search Tree Value II%0A *%0A
  * Given
@@ -1152,17 +1152,60 @@
 _272 %7B%0A%0A
-%09
+    public static class Solution1 %7B%0A        
 public L
@@ -1271,18 +1271,28 @@
 nt k) %7B%0A
-%09%09
+            
 List%3CInt
@@ -1321,18 +1321,28 @@
 ist();%0A%0A
-%09%09
+            
 Stack%3CIn
@@ -1382,18 +1382,28 @@
 cessors%0A
-%09%09
+            
 Stack%3CIn
@@ -1442,18 +1442,28 @@
 essors%0A%0A
-%09%09
+            
 inorder(
@@ -1488,18 +1488,28 @@
 e, s1);%0A
-%09%09
+            
 inorder(
@@ -1534,18 +1534,28 @@
 , s2);%0A%0A
-%09%09
+            
 while (k
@@ -1564,19 +1564,32 @@
  %3E 0) %7B%0A
-%09%09%09
+                
 if (s1.i
@@ -1592,36 +1592,52 @@
 s1.isEmpty()) %7B%0A
-%09%09%09%09
+                    
 res.add(s2.pop()
@@ -1631,35 +1631,48 @@
 .add(s2.pop());%0A
-%09%09%09
+                
 %7D else if (s2.is
@@ -1678,28 +1678,44 @@
 sEmpty()) %7B%0A
-%09%09%09%09
+                    
 res.add(s1.p
@@ -1717,27 +1717,40 @@
 (s1.pop());%0A
-%09%09%09
+                
 %7D else if (M
@@ -1815,95 +1815,187 @@
 ) %7B%0A
-%09%09%09%09res.add(s1.pop());%0A%09%09%09%7D else %7B%0A%09%09%09%09res.add(s2.pop());%0A%09%09%09%7D%0A%09%09%7D%0A%0A%09%09return res;%0A%09%7D%0A%0A%09
+                    res.add(s1.pop());%0A                %7D else %7B%0A                    res.add(s2.pop());%0A                %7D%0A            %7D%0A%0A            return res;%0A        %7D%0A%0A        
 // i
@@ -2011,17 +2011,24 @@
 aversal%0A
-%09
+        
 void ino
@@ -2103,18 +2103,28 @@
 tack) %7B%0A
-%09%09
+            
 if (root
@@ -2139,26 +2139,59 @@
 ) %7B%0A
-%09%09%09return;%0A%09%09%7D%0A%0A%09%09
+                return;%0A            %7D%0A%0A            
 inor
@@ -2253,18 +2253,28 @@
 stack);%0A
-%09%09
+            
 // early
@@ -2320,18 +2320,28 @@
 le tree%0A
-%09%09
+            
 if ((rev
@@ -2410,25 +2410,58 @@
 ) %7B%0A
-%09%09%09return;%0A%09%09%7D%0A%09%09
+                return;%0A            %7D%0A            
 // t
@@ -2491,18 +2491,28 @@
 nt node%0A
-%09%09
+            
 stack.pu
@@ -2529,10 +2529,20 @@
 l);%0A
-%09%09
+            
 inor
@@ -2608,10 +2608,22 @@
 k);%0A
-%09%7D%0A
+        %7D%0A    %7D
 %0A%7D%0A

refactor 272