Recursive function to return last node of a heap

Question

I am trying to return the last node of a binary heap (implemented with pointers, not an array). Here, 'last' means the bottom-most node starting from the left in this case without two children, actually the node where I am supposed to append the new node to. The insert function will bind data to a new node for insertion, then call this function to return the last node, so I can add the new node either left of right depending on the child nodes present, or not.

The problem is that the right side of the tree is always empty, and never gets past the height after root's. Seems to stick on the leftmost side, because it reaches first the exit condition from every recursion call starting from left.

The recursive function checks first the node, returns 0 if no child, returns 1 if only left child and returns 2 in case of a node having two children. Here is the function :

template<typename T>
node<T> * heap<T>::find_insert_pos (node<T> *x, int &res) {
    if(find_insert_poshelper(x, res) == 0) return x;
    else if(find_insert_poshelper(x, res) == 1) return x;
    else {
        node<T> *a = find_insert_pos(x->left, res);
        if(find_insert_poshelper(a, res) != 2) return a;
        else return find_insert_pos(a, res);
        node<T> *b = find_insert_pos(x->right, res);
        if(find_insert_poshelper(b, res) != 2) return b;
        else return find_insert_pos(b, res);
    }
}

I've tried to figure it out, but insertion still goes wrong. The other functions used into insertion are more than triple checked.

(By the way, 'res' is passed by reference always in the chunk of code)

---

I have changed the logic behind the function. Instead of only validating for children per node, I validate now if the node evaluated had children, if it does then I validate one step further each of those children, left and right, to see if any of those grand-children have children themselves.

If they don't, I will loop this for the next level following the root level 0, jumping to level 1 and so on, until one of the children nodes does not contain two children, and returning x.left or x.right, depending the case.

-- Final edit -- Hard to think about a MRE since it was more about logic. The question was posted by someone in need of practice with recursion, and it happened. All the logic changed, even for sub-functions.

But it will be required to manually assign and narrow down until three levels are full (full meaning having two children) before calling this operation, which is checking three levels down. Having this done nicely I get a beautiful heap.

I can show an attempt to a MRE of how I implemented it to be able to find the bottom node to append a new node to, but not pure since I don't put the code from the 'insert' function, which is part iterative (first three levels) and part recursive (that was the original question, to find the parent node for the new node to insert). How the insert operation goes, I create a new node dynamically and then I search for the parent node where I need to append new data to (the iterative part starts here until the 8th node of the tree is reached, path similar to BFS), then when the position is retrieved (that is, the pointer itself), I test whether for left or right insertion, as by the rules of the heap. Starting at the 8th node, the value of the parent node is set recursively as follows :

First the recursive function itself :

    node * function_a (node *x, int &res) {
    node *temp = function_b (x, res);
    if(temp != ptr_null) return temp;
    else {
        if(x->L != ptr_null) function_a (x->L, res);
        if(x->R != ptr_null) function_a (x->R, res);
        return temp;
    }
}

A sub-function :

    node * function_b (node *x, int &res) {
    node *a = x->L;
    node *b = x->R;
    
    int aL = function_c (a->L, res);
    int aR = function_c (a->R, res);
    int bL = function_c (b->L, res);
    int bL = function_c (b->R, res);
    
    if(aL != 2) return a->L;
    else if(aR != 2) return a->R;
    else if(bL != 2) return b->L;
    else if(bR != 2) return b->R;
    else return ptr_null;
}

And another :

    int & function_c (node *x, int &res) {
    if(x->L == ptr_null && x.R == ptr_null) return res = 0;
    else if(x->L != ptr_null && x->R == ptr_null) return res = 1;
    else return res = 2;
}

Since this is checking 3 levels down from x defined (in this case from the root) in function_a, I can't make it 100% recursive that way or I will get a segmentation fault. How can I improve my algorithm ?