Eric S Eric S - 3 months ago 8
C++ Question

Tree Nodes Getting Lost

So I'm trying to do an online assignment (this is not for course credit, I'm taking on my own through coursera) and I'm pretty confused with what's happening.

We are given an 2 line input. The first line is the number of vertices in the tree. The second line lists all the nodes parent nodes with -1 indicating it is the root.

For example, given the following input:

5

4 -1 4 1 1

The first line says there are 5 nodes in total. The second line says node 0 is a child of node 4, node 1
is the root, node 2 is a child of node 4, node 3 is a child of node 1 and node 4 is a child of node 1.

Right now I am just attempting to read in the input and store it in a tree structure.

#include <iostream>
#include <vector>


using namespace std;

struct Node{
int key;
vector<Node*> children;
};


void display(Node* root){
cout << "My Value is " << root->key << endl;
cout << "My children are ";
for (int i = 0; i < root->children.size(); i++){
cout << root->children[i]->key << " ";
}
cout << endl;
for (int i = 0; i < root->children.size(); i++){
display(root->children[i]); //call display on all children
}
cout << endl;
}

int main(){

Node* root = NULL;
int numOfNodes;
cin >> numOfNodes;

int input;
vector<int> parents;
for(int i = 0; i < numOfNodes; i++){
cin >> input;
parents.push_back(input);
}

for(int i = 0; i < parents.size(); i++){
Node *newNode = new Node();
newNode->key = i;
if(parents[i] == -1){ //root node is indicated with a -1 in input
root = newNode;
}
for (int j = 0; j < parents.size(); j++){
if(parents[j] == i){
Node *childNode = new Node();
childNode->key = j;
newNode->children.push_back(childNode);
cout << "value " << newNode->key << " is now a parent of " << childNode->key << endl;
//delete childNode;
}
}
}
display(root);

return 0;
}


I added in the display function to see whether or not I was storing the tree correctly and this is where I'm lost. The print statements I added seem to be conflicting. In main I added a cout whenever I added a childNode however by the time my program gets to the display function is seems the childNodes are missing with the exeception of the children of the root node. Here is a sample of my output.

./treeheight
5
4 -1 4 1 1
value 1 is now a parent of 3
value 1 is now a parent of 4
value 4 is now a parent of 0
value 4 is now a parent of 2
My Value is 1
My children are 3 4
My Value is 3
My children are

My Value is 4
My children are


It would seem that creation of the tree in main worked as I wanted it to but when I try to reference those same nodes in display something is going wrong that I do not understand. I would have thought the output in display would read

My Value is 1
My children are 3 4
My Value is 3
My children are

My Value is 4
My children are 2 0


If anyone could shed some light on what's going on here I would greatly appreciate it.

Answer

When i == 2, you create a node Node(1), and the inner loop finds the two children Node(3) and Node(4). This gives you the following structure:

            Node(1)
             /   \
        Node(3) Node(4)

Then you save this structure in root. So this is saved. Afterwards, when i == 3, you create a new node Node(3). Notice: this is not the same node is the node Node(3) in the tree starting in root. They have the same key, but they are two completely different nodes.

The same thing happens, when i == 4. You create a new node Node(4), which has two children. But this is not the same node as in the tree. It's a new node. And because you don't save the new node with the children Node(0) and Node(1) anywhere, this node gets deleted.

So at the end, you only have the root node and both it's children.

For a solution: you have to store each node somewhere. Don't throw them away. And don't recreate new nodes, when you already created them somewhere. For instance you could create all nodes using a initial for loop and save them in a temporary vector. And afterwards, you copy the pointers to the children-vectors.

Comments