What you implemented is this (in pseudo code):

display(line) {
  if no_x_in(line) {
     print(line)  // instance output and recursion stop 
  } 
  display(replace_first_x_with_0(line))  // recursive call
  display(replace_first_x_with_1(line))  // recursive call
}

• If the string in line contains no x symbols anymore you can output the string and your recursive descent can stop.

• If not, the problem instance is reduced from a line with n times many x symbols into two smaller instances, each with n - 1 many x symbols,

  • one with the x replaced by a 0 symbol and
  • one with the x replaced by a 1 symbol.

which result into a recursive call each. As there are only finite many x symbols in the finite input string, the recursive calls will stop at some point, and the resulting call tree is finite as well.

For your example the call tree is like this:

display('xx') -> issues calls to display('0x') and display('1x')
|
+-> display('0x') -> issues calls to display('00') and display('01')
|   |
|   +-> display('00') -> output, stop
|   +-> display('01') -> output, stop
|
+-> display('1x') -> issues calls to display('10') and display('11')
    |
    +-> display('10') -> output, stop
    +-> display('11') -> output, stop

I think a recursive traversal will be easiest. With a non-recursive solution you end up having to manage the stack yourself.

Here's some code in C#, which you should be able to port to Python easily enough:

string Traverse(Node node)
{
    string rslt = "";
    bool hasRightNode = false;
    bool hasLeftNode = false;
    if (node.Right != null)
    {
        hasRightNode = true;
        rslt = rslt + "(";
        rslt = rslt + Traverse(node.Right);
    }
    if (node.Left != null)
    {
        hasLeftNode = true;
        if (hasRightNode)
        {
            rslt = rslt + ",";
        }
        else
        {
            rslt = rslt + "(";
        }
        rslt = rslt + Traverse(node.Left);
    }
    if (hasLeftNode || hasRightNode)
    {
        rslt = rslt + ")";
    }
    rslt = rslt + node.Value;
    return rslt;
}

The only thing missing is the final semicolon. You can call it with:

string format = Traverse(root) + ";";

Given the tree that you posted, that outputs the expected format string.

Note that I use string concatenation here, which is sub-optimal in C#. If this were a production program, I'd probably use a StringBuilder object to avoid concatenation. I'm not familiar enough with Python to say how best to compose strings in that language.