Assignment

You are expected to create an algorithm to address the requirement presented here. You should

provide an algorithm using pseudocode, explain how it works in general terms (not line by

line), determine its time and space complexities while justifying each of the complexities that

you have identified, as well as provide evidence that your algorithm works (i.e., how do you

know that it works?).

Your algorithm receives a doubly linked list as an input parameter (in the form of a

pointer to the head and a pointer to the tail nodes of the list; see DLList lecture 4). Each

node in the list contains the information: itemCode, name, and price, as depicted below.

The input list is sorted by price.

}

Your algorithm must return a binary search tree (see lecture 7) with the same items as

those in the input. However, they should now be sorted by itemCode.

You should assume that no two items have the same itemCode.

public class ShopNode {

public int itemCode;

public String name;

public double price;

public ShopNode next, prev;

public ShopNode(int i, Strings, double d, ShopNode n, ShopNode p) {

itemCode = i; name=s; price = d; next = n; prev= p;

public ShopNode(int i, Strings, double d) {

this(i,s, d, null, null);

1

,79