Deserialize a binary tree without recursion

Question

I wrote a code for Deserialization of a binary tree using recursion.Can someone help me tweak it in a way that i can eliminate recursion because i have found that i am not allowed to use recursion in my task

#include <stdio.h>
#define NO_CHILD 0
//node
struct Node
{
    int key;
    struct Node* left, *right;
};
//create a node
Node* _NewNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return (temp);
}
//extract binary tree from text
void _ReadBinaryTree(Node *&root, FILE *file)
{
    //read element;if there are no more elements or the elemnt has NO_CHILD stop
    int value;
    if ( !fscanf(file, "%d ", &value) || value == NO_CHILD)
       return;
    //otherwise create the node and recursion for its children
    root = _NewNode(value);
    _ReadBinaryTree(root->left, file);
    _ReadBinaryTree(root->right, file);
}

//preorder traversal
void _Preorder(Node *root)
{
    if (root)
    {
        printf("%d ", root->key);
        _Preorder(root->left);
        _Preorder(root->right);
    }
}
int main()
{
    FILE *file;
    Node *root1 = NULL;
    file = fopen("tree.txt", "r");
    _ReadBinaryTree(root1, file);
    printf("Preorder traversal:\n");
    _Preorder(root1);
    return 0;
}

Here is an example: If i read 1 2 3 4 0 0 0 0 5 0 7 0 0 it will display a binary tree traversed in preorder like this

            1
    2           5
3       4           7

Building a binary tree without recursion? This exercise author has a twisted mind... — Eugene Sh., Jan 24 '18 at 21:36
BTW, as far as I know a single preorder traversal sequence is not sufficient to reconstruct the tree. — Eugene Sh., Jan 24 '18 at 21:39
To do this without recursion, you need a data structure to hold pointers to the nodes along the path to the current node. Implementation details don't matter so much, but it would function basically as a stack. If your Node structure had a parent pointer, then the tree itself would serve that purpose, but I'm supposing that you are not permitted to make that modification. — John Bollinger, Jan 24 '18 at 21:40
Note also that if the zeroes in your example input are supposed to represent the absence of nodes, then your example output does not appear to match that input. — John Bollinger, Jan 24 '18 at 21:46
Why does code use `if ( !fscanf(file, "%d ", &value)...`? `fscanf()` here could return 0,1 or `EOF`. — chux - Reinstate Monica, Jan 24 '18 at 21:48
@EugeneSh., I'm looking at the zeroes in the example input, and thinking that they correspond to the absence of child nodes at corresponding positions in the tree. With that included, I think the pre-order traversal *is* sufficient to reconstruct the tree, though the result is not what the OP presents. — John Bollinger, Jan 24 '18 at 21:48

score 1 · Answer 1 · answered Jan 24 '18 at 21:51

As your example is type of breadth-first algorithm, it may be solved with queue (look at Breadth First Vs Depth First). It is possible also without queue using iterative depth first approach (look at: https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search).

Deserialize a binary tree without recursion

1 Answers1