Implement a binary search tree of positive integers (>0) in LC-3 assembly language. The binary search tree will be manipulated interactively using a menu system with single-letter commands:

P: print the contents of the tree, in order, one per line

I: insert a new value into the tree

R: remove a value from the tree

D: print the maximum depth of the tree

Q: quit the program

For the insert and remove commands, your program will need to read a positive (15-bit) hexadecimal integer value from the keyboard. Write code that will read a positive integer value from the keyboard, one digit at a time, stopping when Enter is pressed, and return it. Input validation and error checking are not required. You may either implement this as a subroutine or as a new TRAP at location x30 that will return the complete value in R0.

You will also need to be able to print positive integers. Again, write either a subroutine or a TRAP at location x31 that will print the value in R0 as a hexadecimal integer.

The rest of the program should use subroutines appropriately.

For the remove operation, you do not need to remove the node from the tree: it is enough to "mark" the node as deleted and ignore it when doing other operations (this is known as "lazy deletion").

For the insert operation, each new node in the tree will be added after the last one in memory, as represented by the LAST label. This will cause the tree to grow forward in memory; the stack of course will grow in the opposite direction. You do not need to implement stack safety, but be careful when testing!

Start out your tree with the data in a4q3-data.asm. You may add extra fields to the nodes, but keep those initial values and its tree structure. The nodes correspond to the following C struct:

struct Node { short value; // though we only use unsigned values struct Node *left_child, *right_child; 7