public class Søketre {
    public static Node settInn(Node v, int x) {
        if (v == null) {
            v = new Node(x);
        } else if (v.element > x) {
            v.venstre = settInn(v.venstre, x);
        } else if (v.element < x) {
            v.høyre = settInn(v.høyre, x);
        }
        return v;
    }

    public static Node finn(Node v, int x) {
        if (v == null) {
            return null;
        }
        if (v.element > x) {
            return finn(v.venstre, x);
        }
        if (v.element < x) {
            return finn(v.høyre, x);
        }
        return v;
    }

    public static Node finnMinste(Node v) {
        if (v.venstre != null) {
            return finnMinste(v.venstre);
        }
        return v;
    }

    public static Node fjern(Node v, int x) {
        if (v == null) {
            return null;
        }
        if (v.element > x) {
            v.venstre = fjern(v.venstre, x);
            return v;
        }
        if (v.element < x) {
            v.høyre = fjern(v.høyre, x);
            return v;
        }
        if (v.venstre == null) {
            return v.høyre;
        }
        if (v.høyre == null) {
            return v.venstre;
        }
        Node u = finnMinste(v.høyre);
        v.element = u.element;
        v.høyre = fjern(v.høyre, u.element);
        return v;
    }

    public static void skrivUtTre(Node v) {
        skrivUtTre(v, 0);
    }

    private static void skrivUtTre(Node v, int nivå) {
        if (v != null) {
            skrivUtTre(v.høyre, nivå + 1);
            for (int i = 0; i < nivå; i++) {
                System.out.print("  ");
            }
            System.out.println(v.element);
            skrivUtTre(v.venstre, nivå + 1);
        }
    }

    public static void skrivUtSortert(Node v) {
        if (v == null) {
            return;
        }
        skrivUtSortert(v.venstre);
        System.out.println(v.element);
        skrivUtSortert(v.høyre);
    }
}