What sort of design pattern should I be using for a structure that can have different states?

I'm making a program that builds mathematical equations into a tree based on operator precedence, e.g. x^2+5*x+1 becomes

           /       \
          /         \
        x^2+5*x  +   1
       /   \ 
      /     \
    x^2  +  5*x
   / \      / \
  x ^ x    5 * x

The data structure I've been using for nodules of the tree is

struct node
{
    std::string eq;
    oper op;
    node * LHS;
    node * RHS;
};

where oper is defined by

enum oper { NONE, ADD, SUB, MULT, DIV, EXP };

The root node of the tree I drew above could therefore be expressed as

{ "x^2+5*x+1", PLUS, ->{ "x^2+5*x", PLUS, ..., ... }, ->{"1", NONE, NULL, NULL} }

if that makes sense.

While I'm writing my algorithm to build this tree, I'm realizing that as this tree gets build its nodes have different "states" which are making my code messy and repetitive when trying to deal with the states. For instance, I have a chunks of code that are like

        if (rootNode == nullptr)
        {
            rootNode = new node;
            rootNode = thisNode;
        }
        else
        {
            if (rootNode->RHS == nullptr)
            {
                rootNode->RHS = thisNode;
            }
            else
            {
                if (thisNode->op < rootNode->op)
                {
                    node * temp = rootNode;
                    rootNode = thisNode;
                    rootNode->LHS = temp;
                }
                else
                {
                    rootNode->RHS = thisNode;
                }

            }
        }

and other stuff where I'm checking whether pointers are NULL and trying to determine how much of the node has been built and yada-yada. I feel like I should be changing my node objects from structs to classes and figuring out some way of making things cleaner, with some sort of "state" that a node has, equivalents of "has a left-hand side and an operator but no right-hand side yet" and so forth.

Any ideas on how I can exploit C++ to do this?