RISC-V ALE Exercise Book v1.3.2

ABI-compliant Recursive Binary Tree Search

Instructions

In this activity, you must write a program in RISC-V assembly language that has a ABI-compliant recursive function int recursive_tree_search(Node *root, int val). Your code will be linked to a code in C that calls the recursive_tree_search function and expects the return value to be the depth of the value if the searched value is present on the tree, 0 if not.

Figure 6.8.1: Binary Tree

The image above shows an example of a binary tree. If the value 361 was being searched, 3 would be the return value of the function, as it is the depth of the value in the tree.

Each tree node is a struct that contains a value on its first position, pointers to the left child and right child on the second and third positions, respectively. In case one of the children does not exist, the pointer will be NULL

lib.h:

typedef struct Node {
    int val;
    struct Node *left, *right;
} Node;

int recursive_tree_search(Node *root_node, int val);
void puts ( const char *str );
char *gets ( char *str );
int atoi (const char *str);
char *itoa ( int value, char *str, int base );
void exit(int code);

Input

Your function will receive the address of the root of the tree on register a0 and the value being searched on register a1.

Check the file example.c to see how your functions will be called. The binary tree used in this example is the same as presented in Figure 6.8.1.

Output

Your function must return on the register a0 the depth of the value if the searched value is present on the tree, 0 otherwise.

Examples

Notes and Tips

• The root node has depth 1.
• The fields of the binary tree node struct are VAL, LEFT and RIGHT, in this order. VAL is a signed int value stored on the node and LEFT and RIGHT are pointers to the node's children. If a node doesn't have one of these - children, the respective pointer will be NULL.
• To check if the received value is on the current node, the comparison VAL = received value must be made.
• A NULL pointer is represented by the value 0.
• All nodes will have different values.
• The utility functions implemented in exercise 6.7 are necessary in this exercise.
• You can test your code using the simulator's assistant from this link.