binary tree from pre-order traversal with absent children specified

Question

I have a binary tree represented by pre-order traversal, which looks like this: {1 4 6 10 0 0 0 7 0 8 0 0 2 5 0 0 3 9 0 0 0 }, where a 0 indicates the absence of child of an element.

How do I construct the original binary tree from this data? I've tried to solve problem with recursion, but I haven't realized how to deal with right children of nodes, as I can't calculate their position in the array unless they have a leaf as a parent (the case when leaf has two zeros after it, which indicate that it has no children).

I feel like the solution has to be pretty easy, but still don't see it.

Answer 1

Something simple like this may work for you. You just need to re build the tree in a pre-order interpretation of the input sequence. The following code doesn't validate the input sequence to check that is a valid tree representation.

struct BTNode {
    int data;
    BTNode* left;
    BTNode* right;
}

BTNode* BuildTree(int* sequence, int& pos) {
    int value = sequence[pos++];
    if (value == 0)
        return nullptr;
    BTNode* node = new BTNode;
    node->data = value;
    node->left = BuildTree(sequence, pos);
    node->right = BuildTree(sequence, pos);
    return node;
}