// 15. hét – A gyakorlati feladatok megoldásai
// Futtatás: java Exercises15.java
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Exercises15 {

    static class Node {
        int key;
        Node left, right;
        Node(int k, Node l, Node r) { key = k; left = l; right = r; }
        Node(int k) { this(k, null, null); }
    }

    static Node insert(Node p, int x) {
        if (p == null) return new Node(x);
        if (x < p.key) p.left = insert(p.left, x);
        else if (x > p.key) p.right = insert(p.right, x);
        return p;
    }

    // F1. Keresőfa-e? Minden csomópont kulcsa a (min, max) intervallumba kell essen
    static boolean isBST(Node p, long min, long max) {
        if (p == null) return true;
        if (p.key <= min || p.key >= max) return false;
        return isBST(p.left, min, p.key) && isBST(p.right, p.key, max);
    }

    // F2. A k-adik legkisebb elem: inorder bejárás k-adik eleme
    static int kth(Node root, int k) {
        List<Integer> l = new ArrayList<>();
        inorder(root, l);
        return l.get(k - 1);
    }

    static void inorder(Node p, List<Integer> l) {
        if (p == null) return;
        inorder(p.left, l);
        l.add(p.key);
        inorder(p.right, l);
    }

    // F3. Intervallum-lekérdezés: a [lo, hi] közé eső kulcsok, csak a szükséges részfákba lépve
    static void range(Node p, int lo, int hi, List<Integer> out) {
        if (p == null) return;
        if (lo < p.key) range(p.left, lo, hi, out);
        if (lo <= p.key && p.key <= hi) out.add(p.key);
        if (p.key < hi) range(p.right, lo, hi, out);
    }

    // F4. Legközelebbi közös ős keresőfában – O(h)
    static int lca(Node p, int a, int b) {
        while (true) {
            if (a < p.key && b < p.key) p = p.left;
            else if (a > p.key && b > p.key) p = p.right;
            else return p.key;
        }
    }

    // F5. Alsó egészrész (floor): a legnagyobb kulcs, amely ≤ x
    static Integer floor(Node p, int x) {
        Integer best = null;
        while (p != null) {
            if (p.key == x) return x;
            if (p.key < x) {
                best = p.key;
                p = p.right;
            } else p = p.left;
        }
        return best;
    }

    // F6. A k legnagyobb elem egy tömbből k méretű MINIMUM-kupaccal – O(n log k)
    static List<Integer> topK(int[] a, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int x : a) {
            pq.offer(x);
            if (pq.size() > k) pq.poll(); // a legkisebbet dobjuk ki
        }
        List<Integer> res = new ArrayList<>(pq);
        res.sort(null);
        return res;
    }

    public static void main(String[] args) {
        Node t = null;
        for (int x : new int[] { 8, 3, 10, 1, 6, 14, 4, 7, 13 }) t = insert(t, x);
        System.out.println("F1. isBST = " + isBST(t, Long.MIN_VALUE, Long.MAX_VALUE));
        Node bad = new Node(8, new Node(3, null, new Node(9)), new Node(10)); // a 9 rossz helyen
        System.out.println("    rossz fa isBST = " + isBST(bad, Long.MIN_VALUE, Long.MAX_VALUE));
        System.out.println("F2. a 3. legkisebb: " + kth(t, 3));
        List<Integer> r = new ArrayList<>();
        range(t, 5, 11, r);
        System.out.println("F3. [5, 11] közöttiek: " + r);
        System.out.println("F4. lca(4, 7) = " + lca(t, 4, 7) + ", lca(1, 13) = " + lca(t, 1, 13));
        System.out.println("F5. floor(5) = " + floor(t, 5) + ", floor(12) = " + floor(t, 12) + ", floor(0) = " + floor(t, 0));
        System.out.println("F6. top 3 [5,1,9,3,7,8,2] = " + topK(new int[] { 5, 1, 9, 3, 7, 8, 2 }, 3));
    }
}