Optimize algorithm for converting “a(b(cd)e(fg))” into a tree

If this was asked at an interview then as the person asking the question I would have expected you to ask a couple of more questions about the input format. What we have here is relatively clear for the simple example but there are some subtitles that come out form this that we need to tease out from the input format.

• How are NULL branches represented?
• How are nodes with the value ')' or '(' represented.
• If we open '(' will there always be two nodes before the ')'

My first problem would be these global variables:

char a[30];
int i=0,n;

Global variables make the code harder to modify and maintain in the long run and should be avoided in most situations. Pass them as parameters and things become much more flexible.

Second point is to declare each variable on its own line (it is much more readable). And try and make the names more meaningful a,i,n hold no meaning so I have no idea what you are going to use them for.

In C I find it usefull to typedef structures to make sure I can use the short version of the name (I have not use C in anger recently so I am not sure if this best practice anymore but I think it makes the code more readable).

typedef struct node
{
    char x;
    struct node *left;
    struct node *right;
} Node;

void tre(struct node * p) //function that I am using to convert the string to a tree

If we are building a tree I would normal expect the return value to be the tree we are building. Not a way of filling out the tree. So I would expect the function signature to look like this:

Node* tre(char const* input)  // potentially more parameters to deal with position.

I find the logic in you main function very hard to follow. You only seem to make nodes if there is an open brace '(' that does not seem correct. You do nothing when there is a close brace? You test if the left on the current node is null but not the right on the current node. I would expect the code to be inherently more symmetrical. The fact that it is not makes it harder to follow.

As an interviewer the things I would have looked for:

• Error checking:
• Binary tree code is inherently symmetrical. Notice that below.
  Doing the left and right branches should look the same.
• the function that parses the input should work on one node:
  You seem to work on one node and part of the next.

I wrote the code and min looks like this:
(Now that I have written it looks identical to Winston)

Node* parseTree(char const* data, size_t* pos)
{
    if (data[(*pos)] == '\0')
    {   // Appropriate error msg
        exit(1);
    }

    // Allocate the tree here. (initialize all members)
    Node*   result  = malloc(sizeof(Node));
    result->value   = data[(*pos)++];
    result->left    = NULL;
    result->right   = NULL;

    // Now check for sub branches.
    if (data[(*pos)] == '(')
    {
        // Move past the '('
        (*pos)++;

        result->left    = parseTree(data, pos);
        result->right   = parseTree(data, pos);

        if ((*pos) != ')')
        {   // Appropriate error msg
            exit(1);
        }
        // Move past the ')'
        (*pos)++;
    }
    // Done.
    return result;
}
Node* buildTree(char const* data)
{
    if (data == NULL)
    {   // Appropriate error msg
        exit(1);
    }
    size_t  pos = 0;
    return parseTree(data, &pos);
}

Perfect in-order traversal of the tree.

But it does not print out what the output should be:

                        a
                       / \
                      b   e
                     / \ / \
                    c  d f  g

To print this you need a couple of things:

• The depth of the tree.
• The max width (related to max depth)
• A breadth first way of printing the tree.

Note: If I was doing the interview I would ask this to make sure you could do a breadth first traversal of the tree. Which involves using a loop rather than recursion.