algorithm - Longest path in binary tree in MIPS

Question

Given binary tree in this way:

.data
tree: .word a
a: .word 5, b, c
b: .word 2, d, e 
c: .word 1, 0, 0
d: .word 5, f, g
e: .word 9, 0, h
f: .word 0, 0, 0
g: .word 6, i, 0
h: .word 55, 0, j
i: .word 4, 0, 0
j: .word 8, 0, 0

The tree looks like this: So the longest path is 7 passing trough i-g-d-b-e-h-j.

So my question is how to implement this? How much space I need to use in the stack?

I need to use 0-4 to the value 4-8 to the left child and 8-12 to the right child?

I mean how do I progress to the next child from the root?

Answer 1

how do I move in this data?

Given a pointer to a node in $a0, the left and right pointers are at 4-byte offsets from the start of the node. (The first member of a node struct appears to be an integer, but you do'nt need to do anything with it.) So lw $t1, 4($a0) loads the 2nd struct member (i.e. node->left), and lw $t2, 8($a0) loads node->right.

You can check for NULL, aka 0, by comparing against the zero-register, like this:
beq $t1, $0, left_was_zero

---

I think your search algorithm should do a tree traversal, and look for the node with the largest maxdepth(left) + maxdepth(right). A normal in-order traversal will consider every node once.

A recursive algorithm, is the obvious way, but you might want to keep some persistent state in registers, i.e. use them as global variables across the recursive calls. So you can keep lots of state "live" in registers instead of actually passing / returning it the way a naive C compiler would. I'm going to represent that using global register variables.

register unsigned longest_len asm("$t8") = 0;
register node* longest_root asm("$t9") = NULL;

// private helper function
// returns max depth, updates global registers along the way
static unsigned traverse(node *root) {
    unsigned left_depth=0, right_depth=0;
    if (root->left)
       left_depth = traverse(root->left);
    if (root->right)
       right_depth = traverse(root->right);

    unsigned sum = left_depth + right_depth;
    if (sum >= longest_len) {
        // update global registers
        longest_len = path + 1;  // path includes *this* node
        longest_root = root;
    }

    // you can probably save an instruction somewhere by optimizing the +1 stuff between the retval and the longest_len check
    int retval = left_depth + 1;   // $v0
    if (left_depth < right_depth)
        retval = right_depth + 1;   // +1 to include this node

    return retval;
}

node *find_longest_path(node *tree) {
    longest_len = 0;
    // longest_root = NULL;  // will always be overwritten
    traverse(tree);
    return longest_root;
}

You could implement this with actual recursion; that may be easier than keeping track of whether you're in the left or right subtree of a node and using a stack data structure on the call-stack. jal / jr with a return address is a convenient way of keeping track of which block to return to.

Anyway, this should translate into MIPS asm pretty straightforwardly; it might even compile (with gcc) using global register variables since I think I used the right syntax for register ... asm("$t9"); https://gcc.gnu.org/onlinedocs/gcc/Global-Register-Variables.html