package problems.medium;

import problems.utils.TreeNode;

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

/**
 * Created by sherxon on 1/6/17.
 */
public class KthSmallestElementinaBST {
    /**
     * This is iterative solution with O(N) space and O(N) time.
     * get kth element from inorder traversal of Binary search tree.
     */

    public int kthSmallest(TreeNode root, int k) {

        List<Integer> list = new ArrayList<>();

        inOrder(root, list);

        return list.get(k - 1);
    }

    void inOrder(TreeNode root, List<Integer> list) {
        if (root == null) return;

        inOrder(root.left, list);

        list.add(root.val);

        inOrder(root.right, list);
    }

    /**
     * Recursive Binary Search method. Time complexity is little higher than previous one but This does not use
     * any extra memory. We can use O(N) space in order to keep size of all nodes to make DP solution.
     */
    public int kthSmallest2(TreeNode root, int k) {
        // int count = nodeCount(root);

        // if (k < count)
        //     return kthSmallest2(root.left, k);

        //  else if (k > count + 1)
        //     return kthSmallest2(root.right, k - 1 - count); // 1 is current node

        // return root.val;
        if (root == null || k < 0):
            return -1
        int leftCount = nodeCount(root.left)
        if (k == leftCount + 1) {
            return root.val
        }
        if (k < leftCount + 1) {
            return kthSmallest2(root.left, k)
        } else {
            return kthSmallest2(root.right, k - 1 - leftCount)
        }
    }

    private int nodeCount(TreeNode root) {

        if (root == null) return 0;

        return nodeCount(root.left) + nodeCount(root.right) + 1;
    }
}

@@ -1289,9 +1289,10 @@
 %3C 0)
-:
+ %7B
 %0A   
@@ -1309,16 +1309,27 @@
 eturn -1
+;%0A        %7D
 %0A       
@@ -1365,16 +1365,17 @@
 ot.left)
+;
 %0A       
@@ -1428,16 +1428,17 @@
 root.val
+;
 %0A       
@@ -1518,16 +1518,17 @@
 left, k)
+;
 %0A       
@@ -1595,24 +1595,25 @@
 - leftCount)
+;
 %0A        %7D%0A 

parsed python to java