Trees

BST Insert

Insert values into a binary search tree by comparing at each node.

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 insert { my ($root, $value) = @_; return node($value) unless defined $root; if ($value < $root->{value}) { $root->{left} = insert($root->{left}, $value); } else { $root->{right} = insert($root->{right}, $value); } return $root; }
my $root; for my $value (4, 2, 6, 1, 3, 5, 7) { $root = insert($root, $value); } print render($root) . "\n";

BST insertion is a comparison path. The pinned tree 4(2(1,3),6(5,7)) is shown with the inserted value taking its sorted slot.

Step 1 - Start at root

For value 5, compare with 4 first; 5 is larger, so move right.

First comparison: 5 > 4, so the search for the insert slot goes right.insert 54compare26137

Step 2 - Take the left slot under 6

At 6, value 5 is smaller, so it becomes the left child.

Second comparison: 5 < 6, so the open left slot is used.426compare135new7

Step 3 - Canonical tree

The resulting tree is the pinned shape 4(2(1,3),6(5,7)).

Final BST after 5 is present under 6.4261357

Complexity

  • Time: O(h) per insert
  • Space: O(n)

Implementation notes

  • node($value, $left, $right) returns a Perl hash reference: { value => $value, left => $left, right => $right }.
  • Missing children are undef; render prints an undefined child as _.
  • Nodes are accessed with hash-reference syntax such as $root->{value} and $root->{left}.
  • my $root starts undefined, then each inserted value reassigns $root = insert($root, $value).
  • insert takes ($root, $value) and returns node($value) when it reaches an undefined subtree.
  • The comparison is numeric: if ($value < $root->{value}).
  • Smaller values recurse left with $root->{left} = insert($root->{left}, $value).
  • All other values recurse right with $root->{right} = insert($root->{right}, $value), so duplicates would follow the right branch in this source.
  • The checked insert order is 4, 2, 6, 1, 3, 5, 7.
  • The trace builds root 4, then attaches 2 on the left and 6 on the right, producing 4(2,6).
  • Inserting 1 follows 4 -> left -> 2 -> left; inserting 3 follows 4 -> left -> 2 -> right, giving 4(2(1,3),6).
  • Inserting 5 follows 4 -> right -> 6 -> left; inserting 7 follows 4 -> right -> 6 -> right, producing 4(2(1,3),6(5,7)).
  • print render($root) . "\n" prints that final tree string instead of dumping Perl object or hash-reference internals.
  • The replay also includes a sorted-insert contrast, 1(_,2(_,3(_,4))), to show the unbalanced height-4 shape without rotations.
binary search tree Values smaller than a node go left; larger values go right.