Program error for frog jump using breadth first search in c++

Question

There are total of 7 spaces, 3 leftmost spaces contain a frog each of one family while the 3 rightmost spaces contain a frog each of second family. The 3 frogs on left need to be transferred to 3 rightmost positions while 3 frogs on right need to be transferred to 3 leftmost positions, but the condition is that each and every one of the frog can jump either to next position in left or right of it (if empty) or to two places to left or right (if empty). Find a suitable set of instructions to get to final position

Initial State(Input): FROG1 FROG1 FROG1 ___ FROG2 FROG2 FROG2

Final State(Output): FROG2 FROG2 FROG2 ___ FROG1 FROG1 FROG1 (where FROG1 denotes frog of first family and FROG2 denotes frog of second family)

I don't know where is it going wrong but after running the code, it shows a warning in swap function that s[index] may be uninitialized. The output is blank whereas expected output should be the steps how the frogs crossed.

My Idea to solve:

The root of this tree is initial state, lets denote the state at one time by "x" to denote frog of 1st family, "o" to denote frog of other family, "-" to denote space. So, the initial state becomes: ooo_xxx and final state is xxx_ooo The root node contains xxx_ooo, and information of its 4 children and its parent. To generate children of a node, just move the space ("-") to left, right, left to left and right to right of its position in parent node, if the state allows, otherwise the child will be null. Keep building the tree until the goal state is found and once the goal state is found print the path in reverse order from that node to root using the pointer of its parent

Approach:

#include <bits/stdc++.h>
using namespace std;

const string finalState = "xxx_ooo";
const string initialState = "ooo_xxx";

struct tree {   
    string s;
    struct tree *one, *two, *three, *four;
    struct tree *parent;
};

struct tree *newNode(string str) {
    struct tree *node;
    node = (struct tree*) malloc(sizeof(struct tree));
    node->s = str;
    node->one = nullptr;
    node->two = nullptr;
    node->three = nullptr;
    node->four = nullptr;
    return node;
}

void display(struct tree *node) {
    struct tree * par = node->parent;
    while(node->parent != nullptr) {
        cout << node->s << endl;
        node = par;
        par = node->parent;
    }
}
string nextState(string s, int choice) {
    int index;
    for(int i = 0; i < static_cast<int>(s.size()); i++) {
        if(s[i] == '_') {
            index = i;
        }
    }    
    if(index + choice >= 0 && index + choice < 7)
        swap(s[index], s[index + choice]);
    return s;
}

void insertUpdated(struct tree *curr, string str, int num) {
    switch(num) {
        case 1: curr->one = newNode(str);
            curr->one->parent = curr;
            break;
        case 2: curr->two = newNode(str);
            curr->two->parent = curr;
            break;
        case 3: curr->three = newNode(str);
            curr->three->parent = curr;
            break;
        case 4: curr->four = newNode(str);
            curr->four->parent = curr;
            break;
    }
}

void generateChild(struct tree *root) {
    queue<struct tree*> q;
    struct tree* ans;
    q.push(root);
    int cnt = 0;
    while(true) {
        struct tree *temp = q.front();
        q.pop();
        cnt++;
        if(temp->s == finalState){
            ans = temp;
            break;
        }
        string s1, s2, s3, s4, curr = temp->s;
        s1 = nextState(curr,-2);
        s2 = nextState(curr,-1);
        s3 = nextState(curr,1);
        s4 = nextState(curr,2);
        insertUpdated(temp, s1, 1);
        insertUpdated(temp, s2, 2);
        insertUpdated(temp, s3, 3);
        insertUpdated(temp, s4, 4);
        q.push(temp->one);
        q.push(temp->two);
        q.push(temp->three);
        q.push(temp->four);
    }   
    display(ans);
}

int main() {
    struct tree *root = newNode(initialState);
    generateChild(root);    
    return 0;
}