Keresőfa

class OSet {
    has( key ) {
        return !this.ik( this.root, key )
    }
    ik(p, key) {
        if (p) {
            if (p.key === key) return false
            else {
                this.up = p
                if ( p.key < key ) {
                    this.rd = true
                    return this.ik( p.r, key )
                } else {
                    this.rd = false
                    return this.ik( p.l, key )
                }
            }
        } else return { key }
    }
    add( key ) {
        if ( this.root ) {
            var uo
            if ( uo = this.ik( this.root, key )) {
                if ( this.rd ) this.up.r = uo
                else this.up.l = uo
                return true
            } else return false
        } else {
            this.root = { key }
        }
        delete this.up
        delete this.rd
    }
    ib( p, f ) {
        if ( p ) {
            this.ib( p.l, f )
            f( p.key, this.i++ )
            this.ib( p.r, f )
        }
    }
    forEach( f ) {
        this.i = 0
        this.ib( this.root, f )
        delete this.i
    }
}

const m = new OSet()

const t = [8, 4, 12, 16, 14, 18, 2, 12, 1, 6, 5, 7]
t.forEach( v => m.add( v ) )

console.log( m.has( 4 ), m.has( 3 ) )

m.forEach( console.log )