Binary Tree Traversal Breadth-first

btree_levelorder.pl

#!/usr/bin/env perl

#####################################################
# Binary Tree Traversal Breadth-first (level order)
# Author: Omid Houshyar
# Date:   11/20/2013
#####################################################

use strict;
use warnings;

my $tree = {
        value => 3,
        left => {
            value => 9,
            left => {
                value => 5,
            },
        },
        right => {
            value => 20,
            left => {
                value => 15,
                left => {
                    value => 33,
                    right => {
                        value => 44
                    },
                },
            },
            right => {
                value => 7,
            },
        },
    };

level_order($tree);

sub level_order {
    my $root = shift;
    my @queue = ($root);

    my $new_row = 0;
    while (scalar @queue) {
        my $node = shift @queue;
        print $node->{value};

        if ($node->{value} eq "\n") {
            $new_row = 0;
        } else {
            print ' ';
        }

        if (exists $node->{left} and defined $node->{left}) {
            unless ($new_row) {
                push @queue, { value => "\n" };
                $new_row = 1;
            }
            push @queue, $node->{left};
        }
        if (exists $node->{right} and defined $node->{right}) {
            unless ($new_row) {
                push @queue, { value => "\n" };
                $new_row = 1;
            }
            push @queue, $node->{right};
        }
    }
}