bintree.pl

use v6;

role Found { has Int $.found is rw }

enum Traversal <pre-order in-order post-order>;

my %root;
for ^20 {
    insert(%root, (0..^1000).pick);
}

say 'Pre order:   ', (gather { show(%root, pre-order)  }).perl;
say 'In order:    ', (gather { show(%root, in-order)   }).perl;
say 'Post order:  ', (gather { show(%root, post-order) }).perl;

while defined (my $sought = prompt('Search? ')) {
    if search(%root, $sought) -> $node {
        say "Found $sought at node #{$node.WHICH}: {$node<VALUE>}";
        if $node<VALUE>.found > 1 {
            say '(again!)';
        }
    }
    else {
        say "No $sought in tree";
    }
}
exit;

sub insert(%tree is rw, Int $val) {
    unless %tree {
        %tree =
            LEFT  => {},
            RIGHT => {},
            VALUE => $val but Found(0),
        ;
        return;
    }
    given %tree<VALUE> {
        when * > $val { insert(%tree<LEFT>,  $val) }
        when * < $val { insert(%tree<RIGHT>, $val) }
        default       { warn "dup insert of $val"  }
    }
}

sub show(%tree, Traversal $method) {
    return unless %tree;
    given $method {
        when pre-order {
            show(%tree<RIGHT>, $method);
            show(%tree<LEFT>, $method);
            take %tree<VALUE>;
        }
        when in-order {
            show(%tree<RIGHT>, $method);
            take %tree<VALUE>;
            show(%tree<LEFT>, $method);
        }
        when post-order {
            take %tree<VALUE>;
            show(%tree<RIGHT>, $method);
            show(%tree<LEFT>, $method);
        }
    }
}

sub search(%tree is rw, $sought) {
    return unless %tree;
    if %tree<VALUE> == $sought {
        %tree<VALUE>.found++;
        return %tree;
    }
    return search(%tree<LEFT>,  $sought) if $sought < %tree<VALUE>;
    return search(%tree<RIGHT>, $sought);
}