Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth

Question

I have tried implementing same in c++. I think I almost got it.However I am getting an error while accessing node from a linked list.

list<list<Node*> > Binary_Tree::level(Node* node)
{
list<Node*> current,parent;
list<list<Node*> > result;

list<Node*>::iterator itr;
if (node != NULL)
current.push_back(node);

while(current.size() > 0)
{
   result.push_back(current);
   parent = current;

   current.clear();
   itr = parent.begin();
   while(itr != parent.end())
   {
     if(itr->left != NULL) // I am getting an error here.error:    request for member ‘right’ in ‘* itr.std::_List_iterator<_Tp>::operator-><Node*>()’, which is of pointer type ‘Node*’ (maybe you meant to use ‘->’ ?
     current.push_back(itr->left);

     if(itr->right != NULL)
       current.push_back(itr->right);

        itr++;
   }

}

return result; }

The items in your current and parent lists are Node*, not Node. Knowing nothing about most of your code beyond what you display here, I believe the syntax you want is (*itr)->left and (*itr)->right, and I highly advise you check *itr against NULL before evaluating either of those. — WhozCraig
– WhozCraig, Commented Feb 28, 2015 at 8:20
Thanks!! It is working now. I will remember your advise too. :) — Prashant Gupta
– Prashant Gupta, Commented Feb 28, 2015 at 8:30
Glad it helped. Btw, anytime you're dealing with breadth algorithms, a queue can sometimes be an intuitive vehicle. See example. Best of luck. — WhozCraig
– WhozCraig, Commented Feb 28, 2015 at 8:48

Prashant Gupta · Accepted Answer · 2015-02-28 09:02:21Z

Here is the solution of above problem. I am putting the complete code.

#include <iostream>
#include <list>

using namespace std;
struct Node{

Node *left;
Node *right;
int data;
Node(int d)
{
  left = NULL;
  right = NULL;
  data =d;
} 
};
class Binary_Tree{

Node *root;
list<list<Node*> > level(Node*);
public:
Binary_Tree()
{
   root = NULL;
} 

  void insert(int element);
  list<list<Node*> > level();

};
void Binary_Tree::insert(int ele)
{
 Node *node = new Node(ele); 
  if (root == NULL)
  {
    root = node;
    return;
  }
  Node* temp = root;
  while(temp != NULL)
  {
    if (ele > temp->data)
    {
      if(temp->right != NULL)
         temp = temp->right;
      else
      { 
        temp->right = node;
        return;
      }
    } 
   else
   {
      if(temp->left != NULL)
        temp = temp->left;
      else
       {
         temp->left = node;
         return;
       }
   }
  }  
}
list<list<Node*> > Binary_Tree::level()
{
   return level(root);
}
list<list<Node*> > Binary_Tree::level(Node* node)
{
   list<Node*> current,parent;
   list<list<Node*> > result;

   list<Node*>::iterator itr;
   if (node != NULL)
   current.push_back(node);

   while(current.size() > 0)
   {
    result.push_back(current);
    parent = current;

    current.clear();
    itr = parent.begin();
    while(itr != parent.end())
    {
     if((*itr)->left != NULL)
      current.push_back((*itr)->left);

     if((*itr)->right != NULL)
       current.push_back((*itr)->right);

        itr++;
   }

}
return result;
}

int main()
{
list<list<Node*> >l;
list<list<Node*> >::iterator itr;
list<Node*>::iterator itr1;

Binary_Tree bt;
bt.insert(3);
bt.insert(2);
bt.insert(4);
bt.insert(1);
bt.insert(5);
l=bt.level();

itr = l.begin();
while(itr != l.end())
{

 itr1 = (*itr).begin();
 while(itr1 != (*itr).end())
 {
     cout<<(*itr1)->data<<" ";
     itr1++; 
 }
 cout<<endl;
 itr++;

} 

return 0;
}

Collectives™ on Stack Overflow

Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related