We will write a seeking algorithm that takes in the file data.bin, which contains a serialized binary tree and reads the array using pre-order notation. The flag can be printed by printing the value when reading each node.
You have been provided data.bin with the serialized array. Each element takes the following form:
| Index | c | left | right |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |The parts of the array entry are:
char.The flag is generated by printing the value at each index when the tree is read using pre-order notation. Please remember that indices are meant for sorting, are not part of the value, and may not be in the correct location in the binary file.
The flag will be represented in ASCII.
Stuck? Open one hint at a time before reading the walkthrough.
This challenge builds a binary tree and then reads it using pre-order notation. We must read the binary, build the tree, and then read the tree using pre-order notation.
Each element contains four pieces: a two-byte index, a one-byte character, a two-byte index for the left child, and a two-byte index for the right. We can use this to define the following struct:
1typedef struct ArrayItem
2{
3 uint16_t index;
4 uint8_t letter;
5 Since the left and the right are indices and not pointers, we use values instead of pointers. We can manage the overhead of connecting the parents to the children later.
We will read the data like the rest of the challenges in this section. First, we open the file and ensure it is properly opened. Then, we initialize the structure holding our nodes and read each node.
First, we open the file. Nothing new here.
1FILE *fp = fopen("data.bin", "rb");
2if (fp == NULL)
3{We can use a static array to hold the structure. This makes a lot of sense because we have the indices of the child nodes. Therefore, if we want to find a child, we can use a sorted copy of the array and access the child by index. This avoids having to link the children.
node *nodes = malloc(100 * sizeof(node));nodes…ls -lh data.bin (you can verify this is 245 bytes) and divide by the struct's size (7 bytes). This gives us 35. We can then allocate the array using this number.Both ways are equally effective.
Now, let's read the data. We can use an infinite while loop that breaks when we no longer read any more bytes. We only need to check when we read the index since we are told each element is complete. This section is almost identical to LinkedOps, except this time, we don't need to check how many bytes to read once we read the opcode.
1uint32_t num_elements = 0;
2while (1)
3{
4 node e;
Once done, we must sort the array to access roots and children by index. We build a compare function that sorts in ascending order based on the index.
1int compare(const void *a, const void *b)
2{
3 node *left Then, we use qsort() to sort the nodes.
qsort(nodes, num_elements, sizeof(node), compare);We need to run a pre-order read on the binary. The best way to do this is to allocate a string and append the letters to the string as we read them. This way, we can print the string at the end as our flag.
A pre-order read is a recursive printing method for a binary tree that prints the current node, the left child, then the right. Our function needs the string storing our pre-order read, a node* to the list of nodes, the index of the node we're currently reading, and then a uint* to the number of nodes we've read thus far.
uint*?Here is the signature of the method we will write:
void preOrder(char *string, node *nodes, uint16_t index, uint16_t *depth);In this method, we need to do three things:
To add the current letter to the string, we can simply access it by index since the string was allocated to the number of nodes. We then update the depth parameter.
1// add current to string
2string[(*depth)++] = nodes[index - 1].letter;Then, we check to see if we're at a leaf node. We can check whether the left and right children are zero. If they are, we can return.
1// make sure we're not at the end
2if (nodes[index - 1].left == 0xffff && nodes[index - 1].Finally, we simply do the recursive travel. We do this by checking if the left child is not null and calling the preOrder method on the left child. Then, we do the same for the right child.
1// perform the recursive traversal
2if (nodes[index - 1].left != 0xffff)
3 preOrder(stringThis is all the processing we need. To start the algorithm, we allocate a string, initialize the depth to zero, and call the method on the root node.
1char *string = malloc((num_elements + 1) * sizeof(char));
2uint16_t Printing the flag is just printing the string:
printf("%s\n", string);Running this gets the flag:
gcc -o solve solve.c && ./solve && rm solveflag{FORGEDTREE}Here is the full solution:
1#include <stdint.h>
2#