#!/usr/bin/env perl

use strict;
use warnings;
use utf8;

use 5.006;

# Start with an empty tree
my $root = undef;

# Read lines one by one
while ( defined( my $line = <> ) ) {

    # Create a new node with this line's value, and empty "left" and "right"
    # references
    my $new = {
        line  => $line,
        left  => undef,
        right => undef,
    };

    # If the tree is empty, this can be our first node; skip the rest of this
    # iteration
    if ( not defined $root ) {
        $root = $new;
        next;
    }

    # Starting at the root ...
    my $cur = $root;

    # Until we don't have any more nodes for comparison (i.e. we've found the
    # place for our new node)...
    while ( defined $cur ) {

        # Decide whether to add this to the "left" subtree or the "right"
        # subtree, depending on whether it's less than the current node or not
        my $dir =
          $line lt $cur->{line}
          ? 'left'
          : 'right';

        # If that reference is undefined, then that's where we'll put this new
        # node; unset $cur so the loop stops
        if ( not defined $cur->{$dir} ) {
            $cur->{$dir} = $new;
            $cur = undef;
            next;
        }

        # Otherwise, we resume descent with the next node
        $cur = $cur->{$dir};
    }
}

# Start a stack of node items to fall back to once we've processed a node, and
# begin at the root
my @stack;
my $cur = $root;

# Keep going as long as there are nodes left in the stack or we have a
# "current" node to print
while ( @stack or defined $cur ) {

    # Drill down through the "left" nodes, stacking them up, until we hit NULL
    while ( defined $cur ) {
        push @stack, $cur;
        $cur = $cur->{left};
    }

    # If there is anything in the stack after doing that, pop off the first
    # one, print it, and then move to its "right" node
    if (@stack) {
        $cur = pop @stack;
        print "\t$cur->{line}";
        $cur = $cur->{right};
    }
}