Creating a binary tree NOT BST

[protater]

I have to create a binary tree with n nodes. I have to take input from a user line by line. Each line has three number. The first number is the value of the node, the second number is which line that node's left node's info is going to be, and the third number is the line in which the right node's info is going to be. An example is 200 1 2 followed by 456 -1 -1 followed by 734 -1 -1. The 0th line is the root. The first line is node 1's info. the second line is node 2's info so the pre order would be 200, 456, 734. The nodes are not always ordered like that, for example 4 2 1, 6 3 -1, 8 4 5, 9 -1 -1,10 -1 -1, 3 -1 -1. The pre order would be 4 8 10 3 6 9.

I know the numbers will be less than 1 million so I use that to keept track of nodes and access them when im on the line that corrseponds to them.

So far the code works for 3 nodes but anything beyond that causes the program to crash. I think it has to do with my find or how I'm linking the nodes. What am i doing wrong?

  #include <iostream>
#include <string>
#include <sstream>
#include <algorithm>


using namespace std;

 struct Node {
    int Data;
    Node* Left;
    Node* Right;
    Node(int val){
    Data=val;
    Left=NULL;
    Right=NULL;
    }

};


Node* Find( Node* node, int value )
{
     if (node == NULL)
    return NULL;
else if (node->Data == value)
    return node;
else {
    Node *left = Find(node->Left, value);
    return left? left: Find(node->Right, value);
}

}


void preOrder(Node *node){

if(node==NULL)
    return;
cout<<node->Data;
cout<<"\n";
preOrder(node->Left);
preOrder(node->Right);

}





int main ()
{
 Node *root=NULL;
 Node *tempN=NULL;
int nNodes=0;
int temp=0;

    std::string input;

    cout<<"N nodes\n";
    cin>>nNodes;
    std::cin.clear();
        std::cin.ignore();

for(int i=0; i<nNodes; i++)
    {


        cout<<"enter num, ln, rn \n";
        std::getline(std::cin, input);
        std::stringstream ss(input);

if(i==0){

ss >>temp;
root= new Node(temp);
ss >>temp;
temp+=1000000;
root->Left=new Node(temp);
ss>>temp;
temp+=1000000;
root->Right=new Node(temp);


}
else{
tempN= Find(root, i+1000000);
if(tempN==NULL)

ss>> temp;
tempN->Data=temp;


ss >>temp;
if(temp!=-1){

temp+=1000000;
root->Left=new Node(temp);
}
ss>>temp;
if(temp!=-1){
temp+=1000000;
root->Right=new Node(temp);
}

}



        }

cout<<"pre order";
preOrder(root);

    return 0;
}

[keskiverto]

Your code (lines 86-91):

else {
 tempN = Find(root, i+1000000);
 if ( tempN==NULL ) {
  ss >> temp;
 }

 tempN->Data=temp; // error, tempN might be null 

Something in that logic ... doesn't it?


Here is something entirely different. For one, it has all input in a vector before creation of the tree. Second, it uses recursion for tree creation.

#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <memory>

struct Foo {
 int data {0};
 int left {-1};
 int right {-1};
};

std::istream & operator>> ( std::istream & in, Foo & ff ) {
 in >> ff.data >> ff.left >> ff.right;
 return in;
}

std::ostream & operator<< ( std::ostream & out, const Foo & ff ) {
 out << std::setw(3) << ff.data << std::setw(3) << ff.left << std::setw(3) << ff.right;
 return out;
}

struct Del {
  template <class T>
  void operator()(T* p) {
    std::cout << "[deleted #" << ( p ? p->data : 0 ) << "]\n";
    delete p;
  }
};

struct Bar {
 int data {0};
 std::unique_ptr<Bar,Del> lef;
 std::unique_ptr<Bar,Del> rig;
};

void tree( std::unique_ptr<Bar,Del> & node, int index, const std::vector<Foo> & src )
{
 if ( 0 <= index && static_cast<size_t>(index) < src.size() ) {
  node.reset( new Bar );
  node->data = src[index].data;
  std::cout << "[created #" << node->data << "]\n";
  if ( index < src[index].left  ) tree( node->lef, src[index].left, src );
  if ( index < src[index].right ) tree( node->rig, src[index].right, src );
 }
}

void print( const std::unique_ptr<Bar,Del> & node )
{
 if ( node ) {
  print( node->lef );
  std::cout << ' ' << node->data;
  print( node->rig );
 }
}

int main ()
{
 std::string input = "4 2 1 6 3 -1 8 4 5 9 -1 -1 10 -1 -1 3 -1 -1";
 std::istringstream IN( input );

 std::vector<Foo> vec;
 vec.reserve( 6 );
 Foo entry;
 while ( IN >> entry ) vec.emplace_back( entry );

 for ( auto x : vec )  std::cout << x << '\n';
 std::cout << '\n';

 std::unique_ptr<Bar,Del> root;
 tree( root, 0, vec );
 std::cout << '\n';
 print( root );
 std::cout << "\n\n";

 return 0;
}

We do not like vector or recursion, do we? We want to iterate and keep less in memory.

#include <iostream>
#include <string>
#include <sstream>
#include <memory>
#include <map>

struct Foo {
 int data {0};
 int left {-1};
 int right {-1};
};

std::istream & operator>> ( std::istream & in, Foo & ff ) {
 in >> ff.data >> ff.left >> ff.right;
 return in;
}

struct Del {
  template <class T>
  void operator()(T* p) {
    std::cout << "[deleted #" << ( p ? p->data : 0 ) << "]\n";
    delete p;
  }
};

struct Bar {
 int data {0};
 std::unique_ptr<Bar,Del> lef;
 std::unique_ptr<Bar,Del> rig;
};

void print( const std::unique_ptr<Bar,Del> & node )
{
 if ( node ) {
  print( node->lef );
  std::cout << ' ' << node->data;
  print( node->rig );
 }
}

int main ()
{
 std::string input = "4 2 1 6 3 -1 8 4 5 9 -1 -1 10 -1 -1 3 -1 -1";
 std::istringstream IN( input );

 std::map<int,std::pair<Bar*,bool>> list;
 std::unique_ptr<Bar,Del> root;
 int row = 0;
 Foo entry;
 while ( IN >> entry ) {
  if ( 0 == row ) {
      root.reset( new Bar );
      Bar * node = root.get();
      node->data = entry.data;
      std::cout << row << " [created #" << entry.data << ']';
      if ( 0 <= entry.left  ) list.emplace( entry.left,  std::make_pair( node, true) );
      if ( 0 <= entry.right ) list.emplace( entry.right, std::make_pair( node, false) );
  }
  else {
      auto it = list.find( row );
      if ( list.end() != it ) {
          if ( it->second.second ) {
            it->second.first->lef.reset( new Bar );
            Bar * node = it->second.first->lef.get();
            node->data = entry.data;
            std::cout << row << " [created #" << entry.data << ']';
            if ( 0 <= entry.left  ) list.emplace( entry.left,  std::make_pair( node, true) );
            if ( 0 <= entry.right ) list.emplace( entry.right, std::make_pair( node, false) );
          } else {
            it->second.first->rig.reset( new Bar );
            Bar * node = it->second.first->rig.get();
            node->data = entry.data;
            std::cout << row << " [created #" << entry.data << ']';
            if ( 0 <= entry.left  ) list.emplace( entry.left,  std::make_pair( node, true) );
            if ( 0 <= entry.right ) list.emplace( entry.right, std::make_pair( node, false) );
          }
          list.erase( it );
      }
  }
  std::cout << " list size " << list.size() << '\n';
  ++row;
 }
 std::cout << "final list size " << list.size() << "\n\n";
 print( root );
 std::cout << "\n\n";

 return 0;
}

What is common in both programs is that a new node is not created before you have data for it.

[protater]

Wow. I did not expect anyone to go into that much detail. Thank you so much for taking the time to show me two different options! That said...I'm still a biginner so a lot of the syntax doesn't really make sense to me. I'm trying to understand the second program. Can you walk me through your logic and your different structures? For example if you have Foo why also have Bar? Thanks again!

[keskiverto]

Your Node and my Bar are equivalent. Read about std::unique_ptr. It is a "smart pointer". When do I call delete to remove the dynamically allocated nodes? When do you?


The input data has triplets of integers. Three integers is not the same as one integer and two pointers. Hence Foo.

When the first node is created (#4), two lines are added into a "table" list:

key addr left
  2  &#4  t
  1  &#4  f

The table has:
"key" the "row" of input
"addr" the address of the "parent node"
"left", boolean whether this node will be the left child of the parent or not.

Second input adds a node (#6), only one line to table, and removes one line:

key addr left
  2  &#4  t
  3  &#6  t

Third input adds a node (#8), again two lines to table, and removes one line:

key addr left
  3  &#6  t
  4  &#8  t
  5  &#8  f

The tree has so far:

   #4
  /  \
#8    #6

The table was created with std::map. It has "key" and "value". The keys are unique. In our map the value is a pair of address and bool.

[protater]

Hmm I see. So you add a node and then put its sub node keys, addr, and whether its left or right. As you read the set of integers, you go through the keys in ascending order and create nodes based on the instructions from the table. So the next set of numbers read will be read and because it's the third one, the key 3 info will be used to create the node and its sub tree info will be added( -1 -1 in this case so nothing added to the table) so the tree would be

#4
/ \
#8 #6
/
#9

the table would be
key addr left
4 &#8 t
5 &#8 f


Am I correct? Once again thanks a lot! You are really helpful!

[protater]

Actually I found a problem. If you get to nth rotation but that key isnt in there yet, the node is not made. Example :std::string input = "11 1 7 12 2 8 13 3 5 14 -1 -1 15 -1 -1 16 -1 -1 17 4 -1 18 -1 9 19 -1 -1 20 6 -1"; Creates the tree with 2 nodes missing.

[keskiverto]

My first program had everything. My second kept only the "already mentioned by parent, but not seen in the input yet" ones. Something has to be kept in "cache" (unless one is willing to read the file back and forth).

Both std::vector and std::map do manage memory dynamically; they can resize during runtime. The list type that you will use must do the same. You can either use a standard library container, like the two above, or create your own (e.g. dynamic array or linked list).

[protater]

Ok. Thanks again for being patient with me. I'm pretty new. Real quick, for your first program I get an error at line 44 because of the > between an int and a unique ptr. Is that just my compiler? Also if I wanted to go off the second program would I just keep a map with the nodes that didnt make it and then just use that to add the nodes after the first run through?

[keskiverto]

My bad. I did test the code before adding the conditional. Updated above.

I think you are right about the second one. Now I see that mine is overly complex.

One could create nodes in advance when the parent says that there will be some, like your program did.
Then add unfinished node(s) to a list like: std::map<int,Node*>

When you do get new data, first check whether the row number is already it the list. (All but root should be there.)
Fill in the details (data) to that node, add possible children, and remove entry from the list.
At the end of input the list should be empty.

If you do know the number of nodes in advance (your program did ask from user) you could use dynamic array as the list:

Node* * list = new Node* [nNodes] {}; // all elements should be nullptr
// or
std::vector<Node*> list( nNodes, nullptr );

Is key in list?

// map version:
auto it = list.find( i );
if ( list.end() != it ) {
  // it is an iterator to list element and can be used

  list.erase(it); // remove entry
}

// array version:
if ( list[i] ) {
  // list element can be used

  list[i] = nullptr; // "remove" entry
}

[protater]

Ok. The first one still doesn't work correctly. "11 1 7 12 2 8 13 3 5 14 -1 -1 15 -1 -1 16 -1 -1 17 4 -1 18 -1 9 19 -1 -1 20 6 -1" it is missing 15 and 17 even though they are added to the input vector. Hmm I just want to make the tree so I can test other orders and reconstructions. Do you recommend to just modify my origial code with a list, or yours with the addition of a new list? I realise that my old code also has the problem of no parent. Using your second program, lets say we do have the two lists. The first list is original with the key addr and left. The second is the Node list for the unfinished nodes. Wouldnt there be a problem with the first list? adding to the first list a node without a yet created parent will mean that it doesnt have an adrr. So even if we have the node and the list, we cant place it. I'm really confused now crap.

[protater]

What about making a vector of nodes and assigning the value and changing just the child pointers if not -1. Shouldn't just that be all I need?

[keskiverto]

The conditions on lines 44 and 45, where I had a logical error, enforce the assumption that a parent appears before its children. That assumption is false on your new data; 15 appears before its parent (17), and 17 before 20. If we remove the conditions and always call the tree(), then the new data is handled nicely.

The second program is harder to modify: it adds nodes to a tree, but those nodes have no parent.
We do know that the the right child of the root (11) will show up on 8th line of input, but at 4th line of input we get value 15 that has no known parent.

What about making a vector of nodes and assigning the value and changing just the child pointers if not -1. Shouldn't just that be all I need?

Yes, but in stages.

If you have a std::vector<Node*> with same size as there will be nodes, then dynamically create the nodes, initializing each with appropriate data.

You have the nodes. Now pass over the array again. For node x, you should have left and right child index stored somewhere. Use those indices (unless -1) to get pointers from the array and update left and right pointer of node x.

[protater]

Yea I see what you're saying. I got it to work too! Thank you so much. You were a big help!