BST Search - Perl DSA

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.

search path A comparison chooses one subtree at each step, so whole branches are skipped.

Visual walkthrough

A BST search follows one comparison path. The same pinned tree shows a found path for 5 and a missing path for 8.

Step 1 - Find 5

Search 5 takes right from 4, then left from 6, then matches 5.

Step 2 - Miss 8

Search 8 takes right from 4, right from 6, right from 7, then reaches null.

Basic Implementation

                            basic.pl
                        

                            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(", ", @_) . "]"; }
sub search { my ($root, $target) = @_; my $node = $root; while (defined $node) { return 1 if $target == $node->{value}; $node = $target < $node->{value} ? $node->{left} : $node->{right}; } return 0; }
my $root = sample_tree(); print(search($root, 5) ? "5 found\n" : "5 not found\n"); print(search($root, 8) ? "8 found\n" : "8 not found\n");

                        

Complexity

Time: O(h) per search
Space: O(1) iterative

Implementation notes

node($value, $left, $right) returns a Perl hash reference with value, left, and right keys.
sample_tree() builds the exact tree 4(2(1,3),6(5,7)).
Child links are either another hash reference or undef.
Node fields are read with hash-reference syntax such as $node->{value}, $node->{left}, and $node->{right}.
search($root, $target) is iterative: it stores the current cursor in my $node = $root.
The loop continues while defined $node; reaching an undefined child exits the loop and returns 0.
A match returns 1 immediately with return 1 if $target == $node->{value}.
Branching uses numeric comparison: $target < $node->{value} ? $node->{left} : $node->{right}.
Searching for 5 visits cursor 4 and branches right, then cursor 6 and branches left, then cursor 5 and matches.
Searching for 8 visits 4 -> right, 6 -> right, and 7 -> right, then reaches an undefined child and returns not found.
The caller prints based on Perl truthiness: search($root, 5) ? "5 found\n" : "5 not found\n" and the same form for 8.
The final output is 5 found followed by 8 not found.