package trees;

public class NthHighestBST {


    /*
     * Find nth highest node in a Binary Search Tree(BST)
     *
     * Runtime Complexity:
     * Linear, O(n)
     *
     * Memory Complexity:
     * O(h)
     *
     *  In-order traversal of BST is always sorted in ascending order.
     *  To find the nth highest node, we will need to scan the tree in descending order that can achieve by doing reverse inorder traversal.
     *  The inorder traversal is normally LVR i.e. Left - Visit - Right. Reverse inorder traversal will be RVL i.e. Right - Visit - Left.
     *  While doing so, we keep a count of nodes seen so far. Once the count reaches n, that is the node to return.
     *
     * */

    private static class Node {
        private int data;
        private Node left, right;

        Node(int item) {
            data = item;
            left = right = null;
        }

        public int getData() {
            return data;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }
    }


    private Node root1;
    protected int currentCount = 0;

    protected Node findNthHighestInBst(Node node, int n) {
        if (node == null) {
            return null;
        }

        Node result = findNthHighestInBst(node.right, n);

        if (result != null) {
            return result;
        }

        currentCount++;
        if (n == currentCount) {
            return node;
        }

        result = findNthHighestInBst(node.left, n);

        if (result != null) {
            return result;
        }

        return null;
    }


    public static void main(String[] argv) {

        NthHighestBST nthHighestBST = new NthHighestBST();
        nthHighestBST.root1 = new Node(100);
        nthHighestBST.root1.left = new Node(50);
        nthHighestBST.root1.right = new Node(200);
        nthHighestBST.root1.left.left = new Node(25);
        nthHighestBST.root1.left.right = new Node(75);
        nthHighestBST.root1.right.left = new Node(125);
        nthHighestBST.root1.right.right = new Node(350);


        int n = 2;
        nthHighestBST.currentCount = 0;
        Node nth_highest_node = nthHighestBST.findNthHighestInBst(nthHighestBST.root1, n);
        System.out.println(String.format(" - %d highest node is %d", n, nth_highest_node.data));

        n = 1;
        nthHighestBST.currentCount = 0;
        nth_highest_node = nthHighestBST.findNthHighestInBst(nthHighestBST.root1, n);
        System.out.println(String.format(" - %d highest node is %d", n, nth_highest_node.data));

        n = 5;
        nthHighestBST.currentCount = 0;
        nth_highest_node = nthHighestBST.findNthHighestInBst(nthHighestBST.root1, n);
        System.out.println(String.format(" - %d highest node is %d", n, nth_highest_node.data));

        n = 30;
        nthHighestBST.currentCount = 0;
        nth_highest_node = nthHighestBST.findNthHighestInBst(nthHighestBST.root1, n);
        System.out.println(String.format(" - %d highest node is %d", n, nth_highest_node));
    }
}