AREA BFS$,$ CODE, READONLY ENTRY NodeSize EQU $4$ ; define a shortcut for the node size $(4$ bytes$)$ LeftChild EQU $4$ ; offset for left child pointer RightChild EQU $8$ ; offset for right child pointer VisitedFlag EQU $12$ ; offset for marking visited nodes UsedFlag EQU $16$ ; offset for marking nodes as processed NextNodeOffset EQU $20$ ; step size for the next node in memory DataCount EQU $15$ ; number of elements in the dataset ; Aliased registers for clarity SortedCounter RN R$8$ ; Keeps track of how many elements are sorted QueueBase RN R$9$ ; Holds the base address of the BFS queue ElementIndex RN R$10$ ; Tracks the current index being processed ; Tree$-$building related registers ListBase RN R$0$ ; Base address of the input array TreeBase RN R$1$ ; Base address of the binary tree structure ListValue RN R$2$ ; Current value from the input array NodeValue RN R$3$ ; Value stored in the current tree node CurrentNodeAddr RN R$11$ ; Tracks the current node's address during traversal ; BFS$-$related registers SmallestValue RN R$0$ ; Stores the smallest value found during traversal AllowAny RN R$1$ ; Indicates if any value can be selected as the smallest SmallestNodeAddr RN R$2$ ; Holds the address of the smallest node found CurrentQueueAddr RN R$11$ ; Tracks the current node being processed in the queue TempStorage RN R$12$ ; Temporary register for intermediate operations ; Initialize the root node of the binary tree InitializeTree LDR ListBase, $=$InputArray ; Load the base address of the input array LDR TreeBase, $=$BinaryTree ; Load the base address of the binary tree MOV CurrentNodeAddr, TreeBase ; Set current node to the root of the tree LDR ListValue, $[$ListBase$]$ ; Load the first element of the array STR ListValue, $[$TreeBase$]$ ; Store it as the root node's value LDR NodeValue, $[$TreeBase$]$ ; Load the root node's value ADD ElementIndex, ElementIndex, #$1$ ; Increment the index counter ; Insert values from the array into the binary tree InsertIntoTree CMP ElementIndex, #DataCount ; Check if all values are processed BGE BeginTraversal ; Start BFS if all values are added ; Load the next value from the input array ADD ListBase, ListBase, #NodeSize ; Move to the next array element LDR ListValue, $[$ListBase$]$ ; Load its value LocateChild LDR NodeValue, $[$TreeBase$]$ ; Load the current node's value CMP ListValue, NodeValue ; Compare it to the value being inserted ADD TreeBase, TreeBase, #NodeSize ; Move to left child pointer ADDGT TreeBase, TreeBase, #NodeSize ; Move to right child pointer if larger ; If a child slot is empty, insert the new node MOV R$5,$ ElementIndex MOV R$6,$ #NextNodeOffset MUL R$7,$ R$5,$ R$6$ ; Compute the offset for the new node ADD R$7,$ R$7,$ CurrentNodeAddr ; Calculate the address of the new node STR ListValue, $[$R$7]$ ; Store the value in the new node LDR R$4,[$TreeBase$]$ ; Load the child pointer value CMP R$4,$ #$0$ ; Check if the slot is empty BEQ AddChild ; If empty, add the node MOV TreeBase, R$4$ ; Otherwise, move to the child node B LocateChild ; Repeat the process AddChild STR R$7,[$TreeBase$]$ ; Set the child pointer to the new node LDR TreeBase, $=$BinaryTree ; Reset the tree pointer to the root ADD ElementIndex, ElementIndex, #$1$ ; Increment the index B InsertIntoTree ; Process the next value ; Initialize BFS traversal BeginTraversal MOV AllowAny, #$1$ ; Allow any value to be considered smallest initially MOV ElementIndex, #$1$ ; Reset the index for the queue MOV CurrentNodeAddr, #$0$ ; Reset the tree traversal index LDR QueueBase, $=$TraversalQueue LDR TempStorage, $=$BinaryTree ; Start from the root node STR TempStorage, $[$QueueBase$]$ ; Add the root to the queue PerformTraversal MOV R$3,$ CurrentNodeAddr ; Store the current tree index MOV R$4,$ #NodeSize ; Node size constant MUL R$5,$ R$3,$ R$4$ ; Calculate the queue offset ADD R$5,$ R$5,$ QueueBase ; Get the address of the current queue element MOV R$3,$ R$5$ ; Get the tree node address from the queue LDR R$3,[$R$3]$ LDR TempStorage, $[$R$3]$ ; Load the node value LDR R$4,[$R$3,$ #UsedFlag$]$ ; Check if the node has been used CMP R$4,$ #$0$ CMPEQ AllowAny, #$1$ ; If any value is allowed, select it MOVEQ SmallestValue, TempStorage MOVEQ AllowAny, #$0$ MOVEQ SmallestNodeAddr, R$3$ ; Update the smallest node's address BNE CompareValues AfterComparison BL CheckChild ; Process the left child BL CheckChild ; Process the right child ADD CurrentNodeAddr, CurrentNodeAddr, #$1$ ; Move to the next queue index CMP CurrentNodeAddr, #DataCount ; Check if traversal is complete MOVEQ TempStorage, #$1$ STREQ TempStorage, $[$SmallestNodeAddr$,$ #UsedFlag$]$ ; Mark the node as used BLT PerformTraversal ; Continue traversal ; Store the smallest value into the sorted array LDR TempStorage, $=$SortedOutput MOV R$3,$ #NodeSize