using System;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    class node{

        public node(int val){

            this.val = val;

        }

        public int val;

        public node left;

        public node right;

        public void add(int val){

            if(this.val == val)

                return;//ignore duplicates

            if(this.val > val){

                if(left == null)

                    left = new node(val);

                else

                    left.add(val);

            }

            else{

                if(right == null)

                    right = new node(val);

                else

                    right.add(val);

            }

        }

        public node next(int v) {

            if(this.val == v)

                return this;

            if(this.val > v)

                return left;

            else

                return right;

        }

        public override string ToString() => val.ToString();

    }

    private static IEnumerable<int> search(node root, int min, int max) {

        HashSet<int> vals = new HashSet<int>();

        node splitN = splitNode(root, min, max, vals);

        LinkedList<node> minNodes = new LinkedList<node>();

        LinkedList<node> maxNodes = new LinkedList<node>();

        if(splitN != null){

            traverse(splitN, min, minNodes);

            traverse(splitN, max, maxNodes);

        }

        else

            Console.WriteLine("splitN null");

        foreach(var n in minNodes) {

            if(n.val >= min)

                vals.Add(n.val);

            addVals(n.right, vals);

        }

        foreach(var n in maxNodes) {

            if(n.val <= max)

                vals.Add(n.val);

            addVals(n.left, vals);

        }

        print(minNodes.Select(x=>x.val));

        return vals;

    }

    private static void addVals(node n, ISet<int> vals){

        if(n == null)

            return;

        vals.Add(n.val);

        addVals(n.left, vals);

        addVals(n.right, vals);

    }

    private static void traverse(node n, int v, LinkedList<node> nodes){

        if(n.val != v){

            var nn = n.next(v);

            if(nn != null){

                nodes.AddLast(nn);

                traverse(nn, v, nodes);

            }

        }

    }

    private static node splitNode(node n, int min, int max, ISet<int> vals){

        if(n == null)

            return null;

        if(n.val >= min && n.val <= max)

            vals.Add(n.val);

        var nA = n.next(min);

        var nB = n.next(max);

        Console.WriteLine(n + " | " + nA + " | " + nB);

        if(nA == nB)

            return splitNode(nA, min, max, vals);

        return n;

    }

    private static void print(IEnumerable<int> vals){

        foreach(var v in vals)

            Console.Write(v + " ");

        Console.WriteLine();

    }

    public static void Main()

    {

        Random rnd = new Random();

        var vals = new HashSet<int>();

        node root = null;

        for(int i=0;i<10;i++){

            int v = rnd.Next(0, 100);

            vals.Add(v);

            if(root == null)

                root = new node(v);

            else

                root.add(v);

        }

        int min = 20;

        int max = 80;

        var inRange = new HashSet<int>();

        foreach(var v in vals)

            if(v >= min && v <= max)

                inRange.Add(v);

        var inRange2 = search(root, min, max);

        Console.WriteLine("====");

        print(vals);

        print(inRange.OrderBy(x=>x));

        print(inRange2.OrderBy(x=>x));

    }

}