jfs

// Assuming the data type looks like this
type
  PBinaryTree = ^TBinaryTree;
  TBinaryTree = record
    data: integer;
    left: PBinaryTree;
    right: PBinaryTree;
  end;

function IsSearchTree(t: PBinaryTree): Boolean;
begin
  // Test if we actually were passed a tree
  // No tree is invalid
  if t = nil then
  begin
    Result := False;
    Exit;
  end;
  // We did get a real tree, test if it's valid
  if (t.left = nil) and (t.right = nil) then
    // Neither a left subtree nor a right subtree
    // This is a single-node tree, always valid
    Result := True
  else if (t.right = nil) then
    // Only the right subtree is empty, test if the left is valid
    Result := (t.data > t.left.data) and // The value at the current node must be larger than the value at the top of the left subtree
              IsSearchTree(t.left) // and the left subtree itself must also be valid
  else if (t.left = nil) then
    // Only left subtree is empty
    // Same as above
    Result := (t.data <= t.right.data) and
              IsSearchTree(t.right)
  else
    // Both a left and right subtree
    // Perform tests on both sides
    Result := (t.data > t.left.data) and
              (t.data <= t.right.data) and
              IsSearchTree(t.left) and
              IsSearchTree(t.right);
end;