Trees

Level-Order Traversal

Visit a tree breadth-first with a queue.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Perl DSA implementation can be compared directly with the rest of the DSA track.

level order Level-order traversal uses a queue to visit shallower nodes first.

Basic Implementation

basic.pl
Replay: real traced execution (multi-file project)
use strict;
use warnings;
sub node { my ($value, $left, $right) = @_; return { value => $value, left => $left, right => $right }; }
sub render {
    my ($node) = @_;
    return "_" unless defined $node;
    return "$node->{value}" unless defined $node->{left} || defined $node->{right};
    return "$node->{value}(" . render($node->{left}) . "," . render($node->{right}) . ")";
}
sub sample_tree {
    return node(4, node(2, node(1), node(3)), node(6, node(5), node(7)));
}
sub list_string { return "[" . join(", ", @_) . "]"; }
my @queue = (sample_tree()); my @output; while (@queue) { my $node = shift @queue; push @output, $node->{value}; push @queue, $node->{left} if defined $node->{left}; push @queue, $node->{right} if defined $node->{right}; } print list_string(@output) . "\n";

  1. tree ← 4(2(1,3),6(5,7)), queue ← [4]

    1use strict;2use warnings;
    values this step4(2(1,3),6(5,7))tree[4]queue

  2. output ← [4], queue ← [2, 6]

    13sub list_string { return "[" . join(", ", @_) . "]"; }14my @queue = (sample_tree()); my @output; while (@queue) { my $node = shift @queue; push @output, $node->{value}; push @queue, $node->{left} if defined $node->{left}; push @queue, $node->{right} if defined $node->{right}; } print list_string(@output) . "\n";
    values this step[4]output[2, 6]queue4dequeued

  3. output ← [4, 2], queue ← [6, 1, 3]

    13sub list_string { return "[" . join(", ", @_) . "]"; }14my @queue = (sample_tree()); my @output; while (@queue) { my $node = shift @queue; push @output, $node->{value}; push @queue, $node->{left} if defined $node->{left}; push @queue, $node->{right} if defined $node->{right}; } print list_string(@output) . "\n";
    values this step[4, 2]output[6, 1, 3]queue2dequeued

  4. output ← [4, 2, 6], queue ← [1, 3, 5, 7]

    13sub list_string { return "[" . join(", ", @_) . "]"; }14my @queue = (sample_tree()); my @output; while (@queue) { my $node = shift @queue; push @output, $node->{value}; push @queue, $node->{left} if defined $node->{left}; push @queue, $node->{right} if defined $node->{right}; } print list_string(@output) . "\n";
    values this step[4, 2, 6]output[1, 3, 5, 7]queue6dequeued

  5. output ← [4, 2, 6, 1], queue ← [3, 5, 7]

    13sub list_string { return "[" . join(", ", @_) . "]"; }14my @queue = (sample_tree()); my @output; while (@queue) { my $node = shift @queue; push @output, $node->{value}; push @queue, $node->{left} if defined $node->{left}; push @queue, $node->{right} if defined $node->{right}; } print list_string(@output) . "\n";
    values this step[4, 2, 6, 1]output[3, 5, 7]queue1dequeued

  6. output ← [4, 2, 6, 1, 3], queue ← [5, 7]

    13sub list_string { return "[" . join(", ", @_) . "]"; }14my @queue = (sample_tree()); my @output; while (@queue) { my $node = shift @queue; push @output, $node->{value}; push @queue, $node->{left} if defined $node->{left}; push @queue, $node->{right} if defined $node->{right}; } print list_string(@output) . "\n";
    values this step[4, 2, 6, 1, 3]output[5, 7]queue3dequeued

  7. output ← [4, 2, 6, 1, 3, 5], queue ← [7]

    13sub list_string { return "[" . join(", ", @_) . "]"; }14my @queue = (sample_tree()); my @output; while (@queue) { my $node = shift @queue; push @output, $node->{value}; push @queue, $node->{left} if defined $node->{left}; push @queue, $node->{right} if defined $node->{right}; } print list_string(@output) . "\n";
    values this step[4, 2, 6, 1, 3, 5]output[7]queue5dequeued

  8. output ← [4, 2, 6, 1, 3, 5, 7], queue ← []

    13sub list_string { return "[" . join(", ", @_) . "]"; }14my @queue = (sample_tree()); my @output; while (@queue) { my $node = shift @queue; push @output, $node->{value}; push @queue, $node->{left} if defined $node->{left}; push @queue, $node->{right} if defined $node->{right}; } print list_string(@output) . "\n";
    values this step[4, 2, 6, 1, 3, 5, 7]output[]queue7dequeued

  9. my @queue = (sample_tree()); my @output; while (@queue) { my $node = s…

    13sub list_string { return "[" . join(", ", @_) . "]"; }14my @queue = (sample_tree()); my @output; while (@queue) { my $node = shift @queue; push @output, $node->{value}; push @queue, $node->{left} if defined $node->{left}; push @queue, $node->{right} if defined $node->{right}; } print list_string(@output) . "\n";
    values this step[4, 2, 6, 1, 3, 5, 7]output

Complexity

  • Time: O(n)
  • Space: O(w) queue space

Implementation notes

  • Nodes are Perl hash references with value, left, and right keys, built by node($value, $left, $right).
  • Node fields are accessed with hash-reference syntax such as $node->{value} and $node->{left}.
  • sample_tree() builds the fixed tree 4(2(1,3),6(5,7)).
  • my @queue = (sample_tree()) stores the root node reference in a Perl array used as the traversal queue.
  • my @output collects visited node values.
  • The loop condition while (@queue) uses @queue in scalar context, so it means "while the queue has length".
  • Dequeue uses my $node = shift @queue, removing the front node reference.
  • Visit writes the scalar value with push @output, $node->{value}.
  • Child enqueue checks defined $node->{left} and defined $node->{right} so undefined children are skipped instead of queued.
  • The trace starts with queue [4].
  • Dequeueing 4 outputs [4] and enqueues [2, 6].
  • Dequeueing 2 outputs [4, 2] and leaves queue [6, 1, 3].
  • Dequeueing 6 outputs [4, 2, 6] and leaves queue [1, 3, 5, 7].
  • The leaf visits then drain the queue through [3, 5, 7], [5, 7], [7], and finally [].
  • list_string(@output) joins the visited values with ", ", so the final print is [4, 2, 6, 1, 3, 5, 7].