tree_refit :: (tree: *Tree, start_index: int) {
    index := start_index;

    while index > 0 {
        i_left   := 2 * index + 1;
        i_right  := 2 * index + 2;
        i_parent := cast(int)floor((index - 1.0) / 2.0);

        // Refit this node to enclose both children
        tree.data[index].bounds = aabb_merge(tree.data[i_left].bounds,
                                             tree.data[i_right].bounds);

        index = i_parent;
    }

    // Refit the root (index 0) separately, since the while loop stops before it
    i_left  := 1;
    i_right := 2;
    tree.data[0].bounds = aabb_merge(tree.data[i_left].bounds,
                                     tree.data[i_right].bounds);
}



tree_rotate :: (tree: *Tree, index_b: int) {
    // B is the node we're considering rotating at
    // Its parent is A, its sibling is C
    i_a := cast(int)floor((index_b - 1.0) / 2.0); // parent
    i_c := (index_b % 2 == 1) ? index_b + 1 : index_b - 1; // sibling

    i_d := 2 * index_b + 1; // B's left child
    i_e := 2 * index_b + 2; // B's right child

    if i_d >= tree.data.count return; // B is a leaf, nothing to rotate

    // Compute cost of current arrangement vs swapping D or E up
    cost_current := surface_area(tree.data[i_b]) + surface_area(tree.data[i_c]);
    cost_swap_d  := surface_area(merge_bounds(tree.data[i_e], tree.data[i_c])) + surface_area(tree.data[i_d]);
    cost_swap_e  := surface_area(merge_bounds(tree.data[i_d], tree.data[i_c])) + surface_area(tree.data[i_e]);

    if cost_current <= cost_swap_d && cost_current <= cost_swap_e return; // already optimal

    if cost_swap_d < cost_swap_e {
        // Swap D and C: just swap their data in the array
        tmp := tree.data[i_d];
        tree.data[i_d] = tree.data[i_c];
        tree.data[i_c] = tmp;
        // Refit B since its children changed
        tree.data[index_b] = merge_bounds(tree.data[i_d], tree.data[i_e]);
    } else {
        // Swap E and C
        tmp := tree.data[i_e];
        tree.data[i_e] = tree.data[i_c];
        tree.data[i_c] = tmp;
        // Refit B
        tree.data[index_b] = merge_bounds(tree.data[i_d], tree.data[i_e]);
    }
    // A's bounds didn't change since D and C are both still under it
}


tree_collapse :: (tree: *Tree, parent_index: int) {
    i_left  := 2 * parent_index + 1;
    i_right := 2 * parent_index + 2;

    // Sanity check — only collapse if both children are leaves
    // (i.e. their own children slots are empty)
    assert(tree_is_leaf(tree, i_left));
    assert(tree_is_leaf(tree, i_right));

    tree.data[i_left]  = EMPTY_NODE;
    tree.data[i_right] = EMPTY_NODE;

    // Parent is now a leaf — update its bounding volume or value here
}

tree_is_leaf :: (tree: Tree, index: int) -> bool {
    i_left  := 2 * index + 1;
    i_right := 2 * index + 2;
    if i_left  >= tree.data.count then return true;
    if i_right >= tree.data.count then return true;
    return is_empty(tree.data[i_left]) && is_empty(tree.data[i_right]);
}