Trees

BST Search

Search a binary search tree for one present and one absent value.

Algorithm

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");

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.

Present search path: 4 -> 6 -> 5.4#126#2135match7

Step 2 - Miss 8

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

Absent search path: 4 -> 6 -> 7 -> null.4#126#21357#3nullnot found

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.
search path A comparison chooses one subtree at each step, so whole branches are skipped.