Task — Binary search tree

You are given a tree. Write a script to find out if the given tree is Binary Search Tree (BST). According to wikipedia, the definition of BST: A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value), and each has two distinguished sub-trees, commonly denoted left and right.

The tree additionally satisfies the binary search property: the key in each node is greater than or equal to any key stored in the left sub-tree, and less than or equal to any key stored in the right sub-tree.

The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another.

Examples

Example 1
Input:
        8
       / \
      5   9
     / \
    4   6
Output: 1 as the given tree is a BST.

Example 2
Input:
        5
       / \
      4   7
     / \
    3   6
Output: 0 as the given tree is a not BST.

Analysis

My solution expects the input to be a data structure with one line per node, containing

node_id, node_key, node side, node_id_of_parent

where node_id is a sequential number (starting from 0), node_side is L or R and node_parent is the node_id of the parent node. The first line is the node_id and key of the root node.

Here is an example tree shown as node_id->key

                         0->50
                _____/           \_____
          1->25                        2->75
        /      \                     /       \ 
   3->12        4->36          5->63           6->88
  /    \       /     \        /      \       /       \
7->6  8->18  9->30 10->42  11->57  12->69  13->82  14->94

To demonstrate a lowest leaf conflicting with the root, change the key of node 10 from 42 to 51.

Try it 

#!/usr/bin/perl
use utf8;
use v5.26;
use strict;
use warnings;

# PWC 130 task 2 - Peter Campbell Smith - 2021-09-13

our @nodes;

read_nodes();
check_nodes();

print qq[This is a valid binary search tree\n];

sub read_nodes {
    
    my ($n, $line, @keys, $junk);
    
    # read in tree
    $n = 0;
    while ($line = <DATA>) {
        @keys = split /[\s,]+/, $line;
        ($nodes[$n]->{id}, $nodes[$n]->{key}, $nodes[$n]->{side}, $nodes[$n++]->{parent}) = @keys;
    }   
}

sub check_nodes {
    
    my ($node_id, $node, $key, $this_node, $parent);

    # loop over nodes
    for $node_id (1 .. $#nodes) {
        $node = $nodes[$node_id];
        $key = $node->{key};
        
        # need to check against every node back up to the root
        $this_node = $node;
        while (1) {
            $parent = $this_node->{parent};
            if ($this_node->{side} eq 'L') {
                is_bad(qq[node $node_id->$key > node $nodes[$parent]->{id}->$nodes[$parent]->{key}]) 
                    if $key > $nodes[$parent]->{key};
            } elsif ($this_node->{side} eq 'R') {
                is_bad(qq[node $node_id->$key < node $nodes[$parent]->{id}->$nodes[$parent]->{key}]) 
                    if $key < $nodes[$parent]->{key};
            } 
            last if $parent == 0;
            $this_node = $nodes[$parent];
        }
    }
}

sub is_bad {
    
    print qq[This is not a valid binary search tree as $_[0]\n];
    exit;
}

__DATA__
0, 50
1, 25,L,0
2, 75,R,0
3, 12,L,1
4, 36,R,1
5, 63,L,2
6, 88,R,2
7,  6,L,3
8, 18,R,3
9, 26,L,4
10,42,R,4
11,57,L,5
12,69,R,5
13,82,L,6
14,94,R,6

41 lines of code

Output

This is a valid binary search tree