Stack Overflow Stack Overflow - 2 months ago 24
C++ Question

Making of a binary tree

I am given a Linked List Representation of complete binary tree in a format like so:

diagram

I have to convert linked list to complete binary tree.I am using a queue to do the same.I am storing the root in the queue storing it in a variable pointing this to a new node which I am making and then storing the left and right pointers and doing this again but I am getting only one node as output when preorder traversal is done on the self made tree.For eg. Linked list is 1->2->3->4->5->NULL but on preorder traversal I am getting 1 as output.

void convert(node *head,TreeNode * &root)
{
if(head==NULL){
root=NULL;
return;
}
queue<struct TreeNode* >Q;
Q.push(root); // Pushing root which is Null at start.
while(head!=NULL){
struct TreeNode * x=Q.front(); // storing
Q.pop(); //Popping
x=new TreeNode; //pointing this null pointer to a new node
x->data=head->data; // storing data
x->left=NULL; //Making left of this point to NuLL
x->right=NULL; //Making right of this point to NuLL
if(!root)root=x; // If root is null point it to x.
Q.push(x->left); // Push the left child pointer which is NULL
Q.push(x->right); // Push the right child pointer which is NULL
head=head->next; // Move further in linked list.
}
}

Answer

I won't post a complete answer, but I'll provide some debugging help.

Here are the first tree iterations of your loop, along with comments about how the variables change.
(It's a very good idea to write things like this down on paper as you trace through the program in your mind. It's less transient than a debugger view, and being able to move back in time while debugging is valuable.)

queue<struct TreeNode* >Q;          // Q: []
Q.push(root);                       // Q: [NULL]
while(head!=NULL){
    struct TreeNode * x=Q.front();  // x = NULL, Q: [NULL]
    Q.pop();                        // Q: []
    x=new TreeNode;                 // x: -> TreeNode {}
    x->data=head->data;             // 
    x->left=NULL;                   // 
    x->right=NULL;                  // x: ->TreeNode {data: data of initial head, 
                                    //                left: NULL, right:NULL}
    if(!root)root=x;                // root: ->TreeNode {data: data of initial head, 
                                    //                   left: NULL, right:NULL}
    Q.push(x->left);                // Q: [NULL]
    Q.push(x->right);               // Q: [NULL, NULL]
    head=head->next;                // Move further in linked list.
}
{
    struct TreeNode * x=Q.front();  // x = NULL, Q: [NULL, NULL]
    Q.pop();                        // Q: [NULL]
    x=new TreeNode;                 // x: -> TreeNode {}
    x->data=head->data;             // 
    x->left=NULL;                   // 
    x->right=NULL;                  // x: ->TreeNode {data: head->data, left: NULL, right:NULL}
    if(!root)root=x;                // root: still ->TreeNode {data: data of initial head, 
                                    //                         left: NULL, right:NULL}
    Q.push(x->left);                // Q: [NULL, NULL]
    Q.push(x->right);               // Q: [NULL, NULL, NULL]
    head=head->next;                // Move further in linked list.
}
{
    struct TreeNode * x=Q.front();  // x = NULL, Q: [NULL, NULL, NULL]
    Q.pop();                        // Q: [NULL, NULL]
    x=new TreeNode;                 // x: -> TreeNode {}
    x->data=head->data;             // 
    x->left=NULL;                   // 
    x->right=NULL;                  // x: ->TreeNode {data: head->data, left: NULL, right:NULL}
    if(!root)root=x;                // root: still ->TreeNode {data: data of initial head, 
                                    //                         left: NULL, right:NULL}
    Q.push(x->left);                // Q: [NULL, NULL, NULL]
    Q.push(x->right);               // Q: [NULL, NULL, NULL, NULL]
    head=head->next;                // Move further in linked list.
}

As you can see, you're pushing and popping a series of null pointers into the queue.
You never use the values from the queue for anything.
You also never modify the root node you created, which is why you only get a one-node tree (the other nodes are just memory leaks).

You could

  • Pop a tree node pointer
  • Get the next two elements from the list (if they exist)
  • Make new nodes from the list elements as appropriate
  • Set the left and right pointers of the popped node to these two new ones
  • Push the new pointers into the queue
  • Repeat