CODEWITHSUNDEEP
c++vector
Jayant Nigam
Jayant Nigam

Reputation: 171

how can I recursively store elements of a Binary Search Tree in a vector in c++

I am trying to store elements of a bst in a vector by inorder traversal but it seems only the first element is getting stored in that vector. In the below program I am giving a set of numbers which will form the bst and then I will run inorder recursive calls and store the elements of that bst in the vector, then in the main() section I'll sort that vector and then print the Kth smallest number.

code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct node
{
   int data;
   node *left;
   node *right;
};

//inserting the data
node *insert(node *r, int data)
{
   if (r == NULL)
   {
      node *newnode = new node();
      newnode->data = data;
      newnode->left = NULL;
      newnode->right = NULL;
      r = newnode;
   }

   else if (data <= r->data)
   {
      r->left = insert(r->left, data);
   }

   else
   {
      r->right = insert(r->right, data);
   }
   return r;
}

//function to extract the elements from the bst
vector<int> inorder(node *r, vector<int> v)
{
   if (r == NULL)
   {
      return v;
   }
   else
   {
      inorder(r->left, v);
      v.push_back(r->data);
      inorder(r->right, v);
   }

   return v;
}

int main()
{

   vector<int> node_data;
   int entries;
   cout << "enter the number of nodes in the bst::" << endl;
   cin >> entries;
   node *root;
   root = new node();
   root = NULL;
   for (int i = 0; i < entries; i++)
   {
      int data;
      cin >> data;
      root = insert(root, data);
   }

   vector<int> v = inorder(root, node_data);
   sort(v.begin(), v.end());
   for (int i = 0; i < v.size(); i++)
   {
      cout << v[i] << " ";
   }
}

please help me find the error in the above code so that all the elements of the bst are stored in that vector

Upvotes: 0

Views: 1167

Answers (1)

stefaanv
stefaanv

Reputation: 14392

For me the glaring error is that you pass the vector by value (and thus make a copy) and you return the updated vector, but you don't store the return value in inorder(r->left, v); and inorder(r->right, v);, so you should decide whether you want to pass the result vector by reference instead or to make sure that you handle the result returned by the inorder() function. Passing by reference is more efficient but not always possible if the result changes depending on what branch you're on (e.g. backtracking), but I think that it works for collecting.

Upvotes: 1

Related Questions